Thread: July 2016
View Single Post
Old 2016-08-06, 22:51   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

56216 Posts
Default

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^(K-1)x4^(K-1) square block (this block is not arbitrary: it comes from a block if we tile the large square with 16 smaller congruent 4^(K-1)x4^(K-1) 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^(N-1)x4^(N-1) congruent square. The missing square will be in exactly one 4^(N-1)x4^(N-1) square: use the induction to tile this with B and L pentominos, for the remaining shape, what is fifteen 4^(N-1)x4^(N-1) 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^(N-2)x4^(N-2) 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^(N-1)x4^(N-1) 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^(N-1)x4^(N-1) square with a missing 4^(N-2)x4^(N-2) 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^(N-1)x4^(N-1) 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.
Attached Thumbnails
Click image for larger version

Name:	pento.png
Views:	58
Size:	5.1 KB
ID:	14749  
R. Gerbicz is offline   Reply With Quote