Author |
Topic: How to approach this proof (Read 1012 times) |
|
fiziwig
Junior Member
Posts: 78
|
 |
How to approach this proof
« on: Apr 7th, 2010, 9:48pm » |
 Quote  Modify
|
Start with the set of all possible generic puzzle pieces, allowing rotation, but not reflection. There are 24 of them.
A subset of 20 of these 24 can be arranged into a 5 x 4 solved puzzle in tens of millions of ways.
However trying to use all of them to make a 6 x 4 completed puzzle seems to be impossible. There don't appear to be any solutions. I'm pretty confident in my computerized exhaustive search, but I'd like a solid proof.
What I've observed (not exhaustively) so far is that it seems that once the straight-edged border is completed, leaving a 2 x 4 open spot to be filled in the middle, there are too many straight-edged slots to be filled for the number of straight edges left among the unused pieces.
I haven't proved this yet, but I'm trying to come up with some kind of pigeon hole approach that shows that it takes too many straight edges to complete the border, leaving too few to complete the middle.
Any suggestions how else I might approach this.
Thanks,
--gary
P.S. Here's a sample 4 x 5 solution: (Letter corresponds to piece letters above, and the digit is rotational orientation; the number of 90-degree clockwise turns)
A0 C1 H1 G3 B2
F2 L3 M3 Q0 I2
R2 T2 W3 O0 N0
E1 J1 P1 K1 D0
|
|
 IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender: 
Posts: 1884
|
|
Re: How to approach this proof
« Reply #1 on: Apr 8th, 2010, 12:02am » |
Quote Modify
|
not being particularly versed in these things, I tackled that by thinking of a female part being -1, male +1, straight line as 0.
The sum from all the pieces would need to be 0, but I make it -2?
0 1 -1 2 0 0
-2 2 0 3 -1 1
-1 -2 1 - 1 -1 -3
4 2 0 0 -2 -4
Whoops. There's an errant - (k) in there.
|
| « Last Edit: Apr 8th, 2010, 12:06am by Noke Lieu » |
IP Logged |
a shade of wit and the art of farce.
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: How to approach this proof
« Reply #2 on: Apr 8th, 2010, 7:34am » |
Quote Modify
|
I tried something similar to that. I think the solution might lie with the distribution of the straight edges. It seems like in every case I've looked at so far even when the required number of straight edges are available, they are distributed incorrectly. E.g., there might be three widely spaced places that need a piece with a straight edge, but the three available straight edges are all on one single piece, and so cannot be distributed around the puzzle as needed.
What makes it tricky is that for the 5x4 finished size there are 30,667,448 solutions! (7,666,862 if rotations and reflections are removed). What is it about making the puzzle one row wider that makes it suddenly unsolvable? It seems there must be some general principle about how many of the 18 pieces with at least one flat side it takes to complete the border for a 6x4, and how many flat side that leaves to complete the interior.
If I start just by enumerating the possible ways to pick the four corner pieces, there are 510 ways, so right off the bat I'd need to have a lot of cases if the proof were to be approach by enumerating cases. There are probably a whole lot of ways the border can be completed, and enumerating all of those would be an even bigger job.
--gary
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: How to approach this proof
« Reply #3 on: Apr 8th, 2010, 8:13am » |
Quote Modify
|
Suppose you have a way of solving the puzzle. Just pay attention to where the pieces A, B, C, H, I, and N have been placed (these are the 6 pieces whose straight edges can't all contribute to filling out the border). I claim that after placing these 6 pieces, there will always be at least 18 straight edges that need to be matched by the other 18 pieces (a rigorous proof of this would probably be tedious, but it seems plausible if you just play around a bit: basically, you start with 20 edges in the perimeter. Adding the three pieces A, B, and C will at most decrease the number of open straight edges by 2, and each of H, I, N can't change the number of open straight edges); however, the other 18 pieces have only 16 straight edges.
|
| « Last Edit: Apr 8th, 2010, 8:15am by Obob » |
IP Logged |
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: How to approach this proof
« Reply #4 on: Apr 8th, 2010, 2:57pm » |
Quote Modify
|
That sounds like a good approach.
So far I have been able to prove that the pieces A, B, and C cannot be used as three of the corners. If they are, then the border cannot be completed.
|
|
IP Logged |
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: How to approach this proof
« Reply #5 on: Apr 9th, 2010, 12:33pm » |
Quote Modify
|
OK Cancel that. There is no proof of impossibility, because while enumerating the perimeter conditions I discovered a solution by hand.
Now I have to figure out where the bug is in my C++ code that told me there were no solutions! I should know better than to trust my own code! 
Solution:
B1 N1 L3 K3 R3 F3
A0 C1 S0 U0 T3 Q0
G2 H1 X0 V0 W1 O0
E1 I3 J1 P1 M1 D0
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: How to approach this proof
« Reply #6 on: Apr 9th, 2010, 12:45pm » |
Quote Modify
|
Ah! Well done. I completely missed the possibility that C (or B -- you can get another solution by making all tabs become holes) goes in the interior, which makes it possible to use the pieces H, I, and N more effectively.
|
| « Last Edit: Apr 9th, 2010, 12:46pm by Obob » |
IP Logged |
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: How to approach this proof
« Reply #7 on: Apr 9th, 2010, 6:28pm » |
Quote Modify
|
And I found the bug in my search program. A typo resulted in it only using 23 of the 24 pieces, so naturally it never found a solution. (It did solve the smaller sized puzzles because those did not require all 24 pieces.)
Once that was fixed it found 410,576 solutions. Removing rotations and reflections leaves 102,644 unique solutions.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: How to approach this proof
« Reply #8 on: Apr 19th, 2010, 7:26am » |
Quote Modify
|
Are there solutions that don't fall apart?
In the one displayed above, the A piece can fall off.
(Just too lazy to write my own program) 
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: How to approach this proof
« Reply #9 on: Apr 19th, 2010, 8:09am » |
Quote Modify
|
No. It is easy to see that the piece A must go on the boundary, since the six pieces with no edges must all go in the middle.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: How to approach this proof
« Reply #10 on: Apr 20th, 2010, 9:26am » |
Quote Modify
|
Hm... it's so obvious even I could have found that. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print