July 2016
[url]https://www.research.ibm.com/haifa/ponderthis/challenges/July2016.html[/url]

A wonderful problem, indeed!

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 '*'."[/CODE] 
I guess that there is a tradeoff there:
if we consider solution using (nonfree) onesided pentominos, then [SPOILER]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.[/SPOILER] 
1 Attachment(s)
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. 
All times are UTC. The time now is 11:25. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.