wu :: forums - Print Page


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

        riddles >> hard >> Heads Up
        
(Message started by: James Fingas on Oct 9^th, 2002, 12:11pm)

Title: Heads Up
Post by James Fingas on Oct 9^th, 2002, 12:11pm

This problem seems so simple, but I think it's impossible :( ... anybody disagree?

3 overlapping circles are drawn to cut the plane into 7 finite regions, each with 3 circular arcs as its boundary. 7 coins are placed, 1 in each region, all Heads-Up. Then a game is played, consisting of a sequence of coin flipping steps. At each step a circle is chosen, and one of the following two operations is performed upon all coins in it:

Operation A: Turn every coin Heads-Up.
Operation B: Reverse every coin.
The object of the game is to put the coin in the central (inside-most) region Heads-Down, and all other coins Heads-Up. Is this objective accomplishable?

Title: Re: Heads Up
Post by Jonathan_the_Red on Oct 9^th, 2002, 2:42pm

It is impossible, and it's simple to prove it. Just try working backwards from the desired end position.

Call a "reverse all" move R, and a "heads up" move H.

Note that first of all, any consecutive strings of R moves is commutative... it doesn't matter what order you do them in. Corrolary: any consecutive string of R moves can be no longer than three moves, and cannot contain the same move more than once.

Note that the last move before the desired end position could not have been an H move and therefore must have been an R move. Because of symmetry, it doesn't matter which circle was the target of the last R move, so pick one at random. Note that the move leading to that position couldn't have been an H move, and couldn't have been an R move on the previous circle, so must have been an R move on one of the two remaining circles. Trying to backtrack from that position leaves the only possible move an R move on the one remaining circle. And there you get stuck: it's still not possible to backtrack an H move, and by the corrolary above, there could be no preceding R move either.

Title: Re: Heads Up
Post by James Fingas on Oct 11^th, 2002, 10:05am

This is an interesting riddle. Let's suppose I draw these three circles, then fiddle around with the coins, and finally figure out that it can't be solved.

Frustrated, I draw another (larger) circle, that encloses the first three. Can I solve the problem now?

Title: Re: Heads Up
Post by Jonathan_the_Red on Oct 11^th, 2002, 12:37pm

[warning: spoiler below]

No, but I can't prove it elegantly. I did it with brute force

Of the 128 possible positions, a total of 112 can be reached using the standard rules. Surprisingly (to me, at least), the exact same set of 112 is reachable when you add the large circle... or, to put it another way, the large circle buys you absolutely nothing. I'm not sure why this should be the case, but it is. (It's obvious why you gain nothing by performing an H move on the large circle, but I would have guessed that an R move would open possibilities that were impossible using the standard rules.)

Title: Re: Heads Up
Post by James Fingas on Oct 11^th, 2002, 1:06pm

I wonder what is so special about those positions that makes it so you can't reach them using the standard moves?

hint: maybe it's because there's an odd number of heads-up in every circle?

Title: Re: Heads Up
Post by Eric Yeh on Oct 11^th, 2002, 3:07pm

Just saw this problem, kinda cool. Got the same soln as Jon (at least looked like it frmo my rel quick read through). Basically, work backwards, see the flipping commutes, leaving four [symmetrically] distinct possibilities, none of which are either the start or could be reached with an all-head op.

Re: James' new prob: but Jon, it's the same pf! You just get eight more (symmetric) posns.

Re: James' final q: Yep, it happens to coincide with exactly the all-circles odd effect. Why? Put a 0 in each sector and flip boolean-ly. Invert one circle at a time in sequence, giving the four distinct possibilities of where you can go from there (i.e. could have come from). If any of the resulting twelve circles (three circles per each of four states) xor-ed w any of your circles gives an all-head config, it let's you invert back using an all-head op. Of course, now we can view the 0's as heads or some such, and one will notice that the set of distinct circles is exactly all those with an even number of 0's...

(Why is getting back to an all-head op suff? It's not hard, but I'll leave it as an ex to the reader! :) )

Best,
Eric

Title: Re: Heads Up
Post by Jonathan_the_Red on Oct 11^th, 2002, 4:34pm

on 10/11/02 at 13:06:20, James Fingas wrote:

I wonder what is so special about those positions that makes it so you can't reach them using the standard moves?

Ahh... that makes the proof obvious. Maybe a little bit too much of a hint, James...

(Eric: Yeah, but I didn't have seven coins handy and didn't feel like working backwards on paper ;) )

Non-brute-force proof spoiler below:

At the beginning, each circle has an even number of heads.

Performing an H move will obviously leave the circle you performed the move on with an even number of heads (although it may leave the other two with an odd number)

Performing an R move toggles all four coins in the circle you're operating on, and two coins in each of the additional circles, which will not alter the parity of any of the three circles.

Therefore, it is not possible for any combination of moves to leave an odd number of heads in all three circles. The desired final position (all heads but the center) has three heads in all three circles and cannot be reached.

Trivially extends to the "big circle" variation.

Title: Re: Heads Up
Post by Eric Yeh on Oct 11^th, 2002, 6:20pm

Jon,

Re: parenthetical: There's actually no additional paper or writing necessary to extend to the big circle case from the previous step.

Re: pf: You've shown necessity, but not sufficiency.

Best,
Eric