July 2016

[Xyzzy]

https://www.research.ibm.com/haifa/p.../July2016.html

[Batalov]

A wonderful problem, indeed!

[R. Gerbicz]

There is an update:

"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 '*'."

[Batalov]

I guess that there is a trade-off there:
if we consider solution using (non-free) one-sided 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 follow-up to enumerate all 3-{one-sided pentomino} meta-solutions.

[R. Gerbicz]

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.