wu :: forums
« wu :: forums - Heads Up »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 3:50am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: SMQ, Grimbal, william wu, Icarus, ThudnBlunder, towr, Eigenray)
   Heads Up
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Heads Up  (Read 3418 times)
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Heads Up  
« on: Oct 9th, 2002, 12:11pm »
Quote Quote Modify Modify

This problem seems so simple, but I think it's impossible  Sad ... 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
**





   
Email

Gender: male
Posts: 102
Re: Heads Up  
« Reply #1 on: Oct 9th, 2002, 2:42pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Heads Up  
« Reply #2 on: Oct 11th, 2002, 10:05am »
Quote Quote Modify 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
**





   
Email

Gender: male
Posts: 102
Re: Heads Up  
« Reply #3 on: Oct 11th, 2002, 12:37pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Heads Up  
« Reply #4 on: Oct 11th, 2002, 1:06pm »
Quote Quote Modify 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
****





   
Email

Gender: male
Posts: 318
Re: Heads Up  
« Reply #5 on: Oct 11th, 2002, 3:07pm »
Quote Quote Modify 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!  Smiley )
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Jonathan_the_Red
Junior Member
**





   
Email

Gender: male
Posts: 102
Re: Heads Up  
« Reply #6 on: Oct 11th, 2002, 4:34pm »
Quote Quote Modify 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 Wink )
 
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
****





   
Email

Gender: male
Posts: 318
Re: Heads Up  
« Reply #7 on: Oct 11th, 2002, 6:20pm »
Quote Quote Modify 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."
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board