7
$\begingroup$

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?

$\endgroup$
4
  • 7
    $\begingroup$ 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. $\endgroup$
    – joriki
    Apr 24, 2011 at 20:48
  • $\begingroup$ @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? $\endgroup$
    – Mark
    Apr 24, 2011 at 21:10
  • $\begingroup$ @joriki after thinking about the problem for a while I think I understand what you mean. $\endgroup$
    – Mark
    Apr 24, 2011 at 21:48
  • $\begingroup$ Well, now I've already spelled it out, so you have the best of both worlds, thinking for yourself and getting an explanation :-) $\endgroup$
    – joriki
    Apr 24, 2011 at 21:55

2 Answers 2

Reset to default
14
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – supercat
    Feb 23, 2014 at 22:09
  • $\begingroup$ How can we prove this to an 8th grader ? That is, what is a simple proof that the first player will always be able to place his coin without overlap ? $\endgroup$
    – Hemant Agarwal
    Jun 19, 2021 at 11:47
0
$\begingroup$

For pennies not touching:

If the first player to move (player A) places a penny at the geometric center of the rectangle and mirrors every move of the opponent, then player A must win because of circular symmetry. I.e., for every move of the opponent, player A has the response of placing a penny at the opposite end of the line determined by the center of the penny placed by the opponent and the geometric center of the rectangle. This argument also works for the case when the pennies must touch. In fact, this argument can be extended to all regularly shaped figures and to any grouping of space-filling tiling pieces, for example pennies and quarters. Just mirror the piece type as well as the position.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .