Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This problem is from The Art and Craft of problem solving book:

Consider the following two player game. Each player takes turns placing a penny on the surface of a rectangular table. No penny can touch a penny which is already on the table. The table starts out with no pennies. The last player who makes a legal move wins. Does the first player have a winning strategy?

Now its not hard to see that the first player will always win if you place the coin in the center. But I have been thinking about what would happen If I also allow Quarter, Loonie and Twoonies. Does the first player have a strategy to always win? Could someone provide an explanation?

share|improve this question
6  
I don't see how that could make a difference. The winning strategy rests on the facts that a) the first player can maintain inversion symmetry and b) the second player can't place a coin such that it covers two points related by inversion symmetry. Neither of these facts changes if different sizes of coins are allowed; in fact even if arbitrary convex shapes are allowed. To cover two points related by inversion symmetry with a coin sitting in the centre would require a non-convex shape. –  joriki Apr 24 '11 at 20:48
    
@joriki unfortunately I do not understand the term inversion symmetry (I tried wiki) or what you mean by covering two points related by inversion symmetry. Could you please elaborate a bit more? –  Mark Apr 24 '11 at 21:10
    
@joriki after thinking about the problem for a while I think I understand what you mean. –  Mark Apr 24 '11 at 21:48
    
Well, now I've already spelled it out, so you have the best of both worlds, thinking for yourself and getting an explanation :-) –  joriki Apr 24 '11 at 21:55

1 Answer 1

up vote 9 down vote accepted

This is an attempt to elaborate on my comment as requested.

"Inversion" refers to an operation that maps each point A to the point B exactly opposite A with respect to the inversion centre, and at the same distance from that centre as A. In coordinates, with the inversion centre at the origin, inversion can be described by changing the sign of all coordinates.

The winning strategy for the first player in the penny game is to place a coin in the centre and from then on place a coin such that it is related to the second player's previous coin by inversion. Two facts are required to make this work:

a) After each move by the first player, the situation must exhibit inversion symmetry; that is, it must be invariant under inversion; that is, if you apply the inversion operation to the entire situation, you end up with exactly the same situation. That guarantees that wherever the second player finds a free spot to play, the opposite spot is also free for you to play.

b) Equally importantly, the second player must not be able to place a coin such that it covers two points related by inversion; that is, it must be impossible to place a coin such that it covers points $A$ and $B$ where the inversion operation maps $A$ to $B$. If such a move were possible, then you couldn't replicate that move in the opposite spot, since the move would occupy $A$ and $B$ at the same time, and you'd also have to occupy $A$ and $B$ to maintain the inversion symmetry, but you're not allowed to do that.

Your modification of the problem by modifying the sizes of the coins obviously doesn't prevent you from maintaining property a) -- you can go on placing coins in the opposite spots like before.

To see that it also doesn't change property b), note that the inversion centre always lies on the line connecting any two points $A$ and $B$ related by inversion. A shape is by definition convex if it contains all points on all line segments between any two of its points. (Clearly a coin is convex in this sense.) But since you placed a coin on the inversion centre in the first move, the second player can never use a convex object to simultaneously cover two points $A$ and $B$ related by inversion, since that would necessarily also cover the inversion centre, which is already occupied.

Thus, as long as there is at least one object exhibiting inversion symmetry that you can use for your first move, and all remaining objects are convex and available in pairs (or in infinite supply), the winning strategy can still be applied.

share|improve this answer
    
What would happen if there were a coin pre-placed in the center of the table, but that coin would be removed as soon as the first player made his move? Would that eliminate any "simple" strategies? The second player could take the center if he wanted, but would not create a symmetric position if he did so. Alternatively, the second player could make a symmetric position, but doing so would allow the first player to take the center and win. –  supercat Feb 23 at 22:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.