10
$\begingroup$

I came across this riddle during a job interview and thought it was worth sharing with the community as I thought it was clever:

Suppose you are sitting at a perfectly round table with an adversary about to play a game. Next to each of you is an infinitely large bag of pennies. The goal of the game is to be the player who is able to put the last penny on the table. Pennies cannot be moved once placed and cannot be stacked on top of each other; also, players place 1 penny per turn. There is a strategy to win this game every time. Do you move first or second, and what is your strategy?

JMoravitz has provided the answer (hidden in spoilers) below in case you are frustrated!

$\endgroup$
14
  • 8
    $\begingroup$ 1. The moves of the game are not defined. 2. I believe this site is for questions to which you don't know the answer. Check out puzzling SE. 3. Is it important that the table is perfectly round? 4. While the bag is infinitely large, what about the number of pennies it has? $\endgroup$
    – Aravind
    Nov 20, 2015 at 15:13
  • 1
    $\begingroup$ got it! For the answer,write your name on a $20 bill and send it to me $\endgroup$
    – DanielWainfleet
    Nov 20, 2015 at 15:13
  • 1
    $\begingroup$ Sorry I forgot that piece (I edited the post). There are actually other shapes that would work besides a circle. $\endgroup$
    – Chris
    Nov 20, 2015 at 15:17
  • 1
    $\begingroup$ Is the bag infinitely large or there is a countable collection of pennies? $\endgroup$
    – AlvinL
    Nov 20, 2015 at 15:23
  • 4
    $\begingroup$ This is a classic puzzle, known even on stackexchange: searching game table pennies found math.stackexchange.com/questions/34911/… $\endgroup$
    – Ethan Bolker
    Nov 20, 2015 at 15:23

4 Answers 4

Reset to default
26
$\begingroup$

Yes, I've seen this one before. Assuming exactly one penny is allowed to be placed per turn:

Go first and place a penny in the dead center of the table. From then on, any move your opponent makes, place a penny in the mirror opposite location (i.e. rotated 180 degrees). It stands to reason that if your opponent's move was valid, yours will be too. Hence, you will always have an available move if your opponent does. Since the table is only finitely large, there can only be finitely many turns, hence you will eventually win.

A more complete proof:

Suppose the table is described using polar coordinates with the center of the table as the origin ($r=0$).

My first move is to place at $r=0$. When my opponent makes a legal move at $(r,\theta)$ I attempt to place a coin at $(r,\theta+180^\circ)$.

Claim: I am always allowed to do so and such a move will always be valid.

Proof: Suppose otherwise. Then that implies that either the target location is not on the table (in which case my opponent's previous move will also have not been on the table and therefore was also invalid), or that target location would have a coin overlap with another previously placed coin. As it could not have been the coin that my opponent has just placed on his last turn (as it is $180^\circ$ away), that implies that those coins must have been placed previously. However... since my moves are always playing $180^\circ$ away from my opponent, that implies that there should be the same situation on the other side of the table and that my opponents coin also is overlapping the corresponding mirrored coins and therefore my opponents move was invalid. Either way, we reach a contradiction implying that if my opponents move was valid that my move is also guaranteed to be valid too.

$\endgroup$
9
  • 7
    $\begingroup$ @mvw None of those are actual counterexamples to the strategy prescribed here. It is not simply by placing in the center alone that allows you to win, but by reacting to the other player's moves in the appropriate way. While yes, there exist packings of circles within circles that allow either an even or an odd number of circles, any packing with $180^\circ$ rotational symmetry with a circle in the center must have an odd number of circles. $\endgroup$
    – JMoravitz
    Nov 20, 2015 at 15:32
  • 8
    $\begingroup$ Case 8 in the page you linked does not have $180^\circ$ rotational symmetry. While it does have some rotational symmetry, it is not specifically $180^\circ$ rotational symmetry. Once the other player places a penny, I as the first player will place the penny at the location $180^\circ$ away, thus avoiding that picture as a possibility. $\endgroup$
    – JMoravitz
    Nov 20, 2015 at 15:37
  • 4
    $\begingroup$ @mvw yes, I understood your link: the one with a circle in the center and seven circles around the outside, which has $k\frac{360^\circ}{7}$ symmetry for any $k=1,2,\dots,7$ but not $180^\circ$ symmetry. $\endgroup$
    – JMoravitz
    Nov 20, 2015 at 15:42
  • $\begingroup$ @mvw I think perhaps you are getting thrown off my my use of the word "mirror opposite." By that I mean specifically 180 degree rotation which is equivalent to reflecting about the line orthogonal to the ray pointing to my opponent's move. $\endgroup$
    – JMoravitz
    Nov 20, 2015 at 15:54
  • 1
    $\begingroup$ None of those counter examples, including #8. Will occur if player #1 is using the strategy. In example #8, for example, player 1 will play the center penny. Player #2 plays one of the edges. Player 1 will then play the position directly across. That did not happen in example 8. Player 1 can guarantee and assure 1) Penny in center 2) 180 degree symmetry. Only examples # 7, 9, and 19 have this. In those three cases player 1 wins. $\endgroup$
    – fleablood
    Nov 20, 2015 at 16:02
0
$\begingroup$

JMoravitz has a great post. I'm happy to have arrived at the same answer, and would like to share a thought that aided my process. Consider an extreme case to find out whether to go first or second:

The problem specifies pennies and a circular table. If there is a winning strategy, then without any loss of generality, we ought to win regardless of the radius of the table. Given a table whose radius is smaller than the penny's, and assuming that at least one penny would fit on the table, then you clearly want to go first. You would immediately win.

What if the table was... well... normal? How to ensure your win? Don't run out of options, of course. This is the same idea as J's in the other answer.

Given the centrosymmetric nature of the arrangement, after centering your original penny, player two can now be mimicked until the game's end. For any penny the opponent places at $(x,y)$, place your next one at $(-x,-y)$. I'd expect most opponents to resign after a turn or two, or suffer a slow, sad defeat.

Zugzwang after move 1 really.

$\endgroup$
1
  • $\begingroup$ I've often found this technique of thinking of an extreme case to be useful. Does this method have an official name? $\endgroup$
    – Roger Dahl
    Nov 21, 2015 at 16:08
0
$\begingroup$

I'm wondering if it would be possible to prove that the following solution is a winning or losing strategy:

Go first and place a penny near the edge of the table in such a way that there isn't room for another penny on the outside of it.

$\endgroup$
-1
$\begingroup$

Update: OP changed rules at revision 3.

My attempt as spoiler below.

I move first and cover the whole table with pennies.

$\endgroup$
5
  • $\begingroup$ But only one penny is allowed per turn $\endgroup$
    – Shailesh
    Nov 20, 2015 at 15:28
  • $\begingroup$ OK. That explains it. Fine. $\endgroup$
    – Shailesh
    Nov 20, 2015 at 15:29
  • $\begingroup$ Hilarious! +1${}$ $\endgroup$
    – user856
    Nov 20, 2015 at 15:50
  • $\begingroup$ So, if $O$ is player $1$'s first play, and $A$ is player $2$'s first play. then player $1$'s second play will be at $(0,-2)$, not at $(2,1.8)$. Again, this is not a counter example as it does not follow the strategy outlined. With perfect play, player $1$ will win. With poor play either player can win. The question was not about who can win, but about who will win given perfect play by both players. $\endgroup$
    – JMoravitz
    Nov 20, 2015 at 15:55
  • $\begingroup$ perhaps Joriki's answer will provide a better explanation to you. Just remember that in the proposed strategy, the only person making any decisions will be the second player. All of the first player's choices are predetermined based on what the second player does. $\endgroup$
    – JMoravitz
    Nov 20, 2015 at 16:03

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