20160702, 13:30  #1 
"Mike"
Aug 2002
3×2,731 Posts 
July 2016

20160704, 01:02  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,461 Posts 
A wonderful problem, indeed!

20160704, 18:25  #3 
"Robert Gerbicz"
Oct 2005
Hungary
10111000101_{2} Posts 
There is an update:
Code:
"Update (3/7): Your pentominos should be able to tile all the 4^N*4^N boards with any possible missing square. You can use free pentominos (rotation and reflections are allowed). Solving with less than three pentominos types will earn you a '*'." 
20160704, 19:12  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,461 Posts 
I guess that there is a tradeoff there:
if we consider solution using (nonfree) onesided pentominos, then the solution(s?) exists with three, but two of them [I]can[/I] be reflections of one free pentomino. Makes for an interesting followup to enumerate all 3{onesided pentomino} metasolutions. 
20160806, 22:51  #5 
"Robert Gerbicz"
Oct 2005
Hungary
10111000101_{2} Posts 
My sent solution also used P and L (but named P as B), [I would say my solution has a nicer tiling of the larger version of P and L] :
I'll use only two types of pentominos, (see the attached pento.jpg file [[used Windows paint]] for the pictures and further tilings), so using B and L pentominos. The case N=1 is trivial, using symmetry there is only 3 cases, see the tilings (S1,S2,S3) for these cases using only B and L.. For larger N values we use induction in the following way: suppose that the tiling for smaller K<N values is possible and it is also possible to tile those (4^K)x(4^K) grids where it has a missing 4^(K1)x4^(K1) square block (this block is not arbitrary: it comes from a block if we tile the large square with 16 smaller congruent 4^(K1)x4^(K1) square). For N=1 this is true (the statement is the same for the two conditions in the induction). Suppose that for K<N the induction is true, we need it for N. For the first part in the induction we need a tiling of 4^Nx4^N square where it has a missing square, make the standard tiling of the big square with the 16 smaller 4^(N1)x4^(N1) congruent square. The missing square will be in exactly one 4^(N1)x4^(N1) square: use the induction to tile this with B and L pentominos, for the remaining shape, what is fifteen 4^(N1)x4^(N1) square's tiling use the second part of the induction: it is a 4 times magnification (in both x and y direction) of the same shape that comes from fifteen 4^(N2)x4^(N2) square, using induction it has a tiling, use that and do the 4 times magnification. It is not a valid tiling, but we can tile with B and L the four times magnification of B and L, see B4 and L4 in pento.jpg (note: trivially we can use 2 B to get a tile of a 2x5 rectangle, those rectangle tilings are not shown in the file, only the white rectangles). With this we got a valid tiling of 4^Nx4^N with a missing square. For the second part of the induction: we have a 4^Nx4^N grid with a missing 4^(N1)x4^(N1) square (it is one of the 16 square coming from a regular tiling). But this shape is also a 4 times magnification of a smaller 4^(N1)x4^(N1) square with a missing 4^(N2)x4^(N2) square. Use induction, it has a valid tiling, do the magnification and the tilings of B4 and L4 as above to get a good tiling of the 4^Nx4^N square with a missing 4^(N1)x4^(N1) block. With this we finished the proof of the induction, hence our statement is valid so for each N we have a tiling, what we needed. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
July 2017  R. Gerbicz  Puzzles  6  20170808 22:58 
July 2015  Xyzzy  Puzzles  16  20150819 16:13 
July 2014  Xyzzy  Puzzles  6  20141102 19:05 
Happy July 4th  LaurV  Lounge  8  20120706 00:13 
Max on the move: vacation June 28/30July 4  mdettweiler  No Prime Left Behind  8  20090705 05:20 