wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> How to approach this proof
        
(Message started by: fiziwig on Apr 7^th, 2010, 9:48pm)

Title: How to approach this proof
Post by fiziwig on Apr 7^th, 2010, 9:48pm

Start with the set of all possible generic puzzle pieces, allowing rotation, but not reflection. There are 24 of them.

http://fiziwig.com/puzzle_pieces.gif

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

Title: Re: How to approach this proof
Post by Noke Lieu on Apr 8^th, 2010, 12:02am

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.

Title: Re: How to approach this proof
Post by fiziwig on Apr 8^th, 2010, 7:34am

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

Title: Re: How to approach this proof
Post by Obob on Apr 8^th, 2010, 8:13am

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.

Title: Re: How to approach this proof
Post by fiziwig on Apr 8^th, 2010, 2:57pm

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.

Title: Re: How to approach this proof
Post by fiziwig on Apr 9^th, 2010, 12:33pm

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:

http://fiziwig.com/puzzle_solved.gif

B1 N1 L3 K3 R3 F3

A0 C1 S0 U0 T3 Q0

G2 H1 X0 V0 W1 O0

E1 I3 J1 P1 M1 D0

Title: Re: How to approach this proof
Post by Obob on Apr 9^th, 2010, 12:45pm

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.

Title: Re: How to approach this proof
Post by fiziwig on Apr 9^th, 2010, 6:28pm

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.

Title: Re: How to approach this proof
Post by Grimbal on Apr 19^th, 2010, 7:26am

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) ;)

Title: Re: How to approach this proof
Post by Obob on Apr 19^th, 2010, 8:09am

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.

Title: Re: How to approach this proof
Post by Grimbal on Apr 20^th, 2010, 9:26am

Hm... it's so obvious even I could have found that. :-/