Author |
Topic: Heads Up (Read 3437 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
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?
|
|
 IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
 |
Re: Heads Up
« Reply #1 on: Oct 9th, 2002, 2:42pm » |
 Quote  Modify
|
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.
|
|
IP Logged |
My arcade cabinet
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Heads Up
« Reply #2 on: Oct 11th, 2002, 10:05am » |
Quote Modify
|
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?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: Heads Up
« Reply #3 on: Oct 11th, 2002, 12:37pm » |
Quote Modify
|
[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.)
|
| « Last Edit: Oct 11th, 2002, 12:37pm by Jonathan_the_Red » |
IP Logged |
My arcade cabinet
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Heads Up
« Reply #4 on: Oct 11th, 2002, 1:06pm » |
Quote Modify
|
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?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Heads Up
« Reply #5 on: Oct 11th, 2002, 3:07pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: Heads Up
« Reply #6 on: Oct 11th, 2002, 4:34pm » |
Quote Modify
|
on Oct 11th, 2002, 1:06pm, 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.
|
| « Last Edit: Oct 11th, 2002, 4:34pm by Jonathan_the_Red » |
IP Logged |
My arcade cabinet
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Heads Up
« Reply #7 on: Oct 11th, 2002, 6:20pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print