mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-07-02, 13:30   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

1D8916 Posts
Default July 2016

https://www.research.ibm.com/haifa/p.../July2016.html
Xyzzy is offline   Reply With Quote
Old 2016-07-04, 01:02   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

13×17×41 Posts
Default

A wonderful problem, indeed!
Batalov is offline   Reply With Quote
Old 2016-07-04, 18:25   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101010100112 Posts
Default

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 '*'."
R. Gerbicz is offline   Reply With Quote
Old 2016-07-04, 19:12   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

13·17·41 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2016-08-06, 22:51   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

29×47 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:	57
Size:	5.1 KB
ID:	14749  
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
July 2017 R. Gerbicz Puzzles 6 2017-08-08 22:58
July 2015 Xyzzy Puzzles 16 2015-08-19 16:13
July 2014 Xyzzy Puzzles 6 2014-11-02 19:05
Happy July 4th LaurV Lounge 8 2012-07-06 00:13
Max on the move: vacation June 28/30-July 4 mdettweiler No Prime Left Behind 8 2009-07-05 05:20

All times are UTC. The time now is 12:55.

Mon Jul 13 12:55:11 UTC 2020 up 110 days, 10:28, 1 user, load averages: 1.95, 1.96, 2.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.