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 is inspired by the question at Game about placing pennies on table

"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?"

The first player will win by placing a penny in the centre of the table, then can always symmetrically match the opponent's moves reflecting across the central point (assuming equivalent dexterity), until the second player has no remaining move.

However, suppose we are playing as the second player, and we observe that the first player does not know this strategy - it appears that the first player has played in a 'random' (edit: leaving a central play possible) position on the board.

Can the second player use this bad first move to create a winning strategy? Even if the first player then returns to playing 'perfectly'? How?

If not, what is the second player's best option for a chance to win?

Further to discussion: If the first player can return to play in the centre later on (or, even if the second player plays directly in the centre), the first player will take back their winning strategy.

Can the second player partially cover the centre enough in order to prevent this/gain the "central play" advantage? Can we be specific about what the second player should do in each case?

share|improve this question
    
A quick (and somewhat boring) counter-example: if the table can only fit one penny (say, if its side length is $2R(1+\epsilon)$, $R$ being the penny's radius) then the first player wins anyway. –  yohBS Apr 8 '12 at 11:28
    
in that case we might say the first player played in the centre of the table ;) –  Ronald Apr 8 '12 at 11:32
    
@yohBS I edited the question, thanks :) –  Ronald Apr 8 '12 at 11:33
    
We might say that, but we don't have to. That is exactly my point. I don't know what the answer is, but you see immediately that it might depend on the the table size. So this might turn out to be ugly... –  yohBS Apr 8 '12 at 11:34
1  
It is not obvious that if the first player can play the center later on, he has a guaranteed win. The strategy relies on symmetry and the symmetry may be broken by the plays so far. It may be a winning move, but it may also not be. –  Ross Millikan Apr 10 '12 at 13:52
show 2 more comments

4 Answers 4

up vote 6 down vote accepted
+50

Considering similar games, I don't think that the second player necessarily will have a winning strategy. Either the first or the second player will have a winning strategy, but which player will depend on the dimensions of the board.

The "gold standard" of a strategy for impartial games like this involves a Grundy function $G$, which always exists (Sprague-Grundy theorem) but can be hard to find. It takes a board position as input and returns a non-negative integer. It returns a positive number for first player wins and zero for second player wins.

With $G$, the problem of perfect play is solved: Consider all the board positions $P_i$ that you could move to. If there's a position such that $G(P_i)=0$, then move there... and your opponent has no hope.

$G$ has these properties:

  • During the endgame, there will be a few "islands" in the sea of pennies where one can still play. Each island is a mini-board with its own Grundy value. The Grundy value of the entire board is the bitwise XOR, a.k.a. nim-sum, of the Grundy values of the islands.

  • If you are at board position $P$, and can move to any one of the board positions $P_i'$, then $G(P) = mex(G(P_i'))$, where "mex" means the minimum excluded value. That is, the least non-negative integer not in the set $\{G(P_i')\}$.

To train myself to play against other people, I would study the Grundy values of small board positions. I would write a computer program to draw bunches of them grouped by their Grundy values, then look for patterns. My strategy would be to avoid symmetry and place the pennies to create islands with known Grundy values. Then play perfectly just in the end-game.

In the game Cram, players place 1x2 dominoes on a square grid. The last player who makes a legal move wins. From the table of Grundy values in Wikipedia's page on Cram, you can see that:

  • 4x4, 5x5, and 4x6 islands are first-player wins.
  • 4x5 and 5x7 islands are second player wins.
  • There's not much else known about who wins despite a lot of searching by computer.
share|improve this answer
    
+1, nice answer! –  joriki Apr 16 '12 at 10:39
add comment

If the distance between the center of the first penny and the center of the table (which I'll call the origin) is between $R$ and $\sqrt 3 R$, where $R$ is radius of the pennies, mirroring the first player's moves is a winning strategy for the second player. This is because it is always possible to mirror a penny that does not cover the origin, and two opposite pennies placed as above leave no room on either side to sneak in a penny that does cover the origin.

share|improve this answer
    
ok... so if the first penny is sufficiently close to the centre that a mirror coin doesn't leave space for a central coin, the second player can 'steal' the first player's mirroring strategy. –  Ronald Apr 8 '12 at 12:25
    
Why $\sqrt{3}R$ rather than $2R$? –  Ronald Apr 8 '12 at 12:27
    
suggestion: if the first penny doesn't have this condition, then the second player has the opportunity to place a penny which does follow this condition. –  Ronald Apr 8 '12 at 12:28
1  
Because if the first penny is at slightly under $2R$, and the second penny mirrors the first, there is still room to fit in another penny -- not directly between them, but a little off to the side -- that does cover the origin. –  Rahul Apr 8 '12 at 13:07
    
Like! but this creates a curious asymmetry which might affect the strategic advantage of playing at the origin? –  Ronald Apr 8 '12 at 14:11
add comment

Assume the player must place the penny on a lattice-point:

If the table contains an even number of lattice-points, the second player always wins. An odd number of points and the first player always wins.

If the player can place the penny on a lattice-line, thus blocking two lattice-points, then the above still holds (the evenness-oddness of the count does not change).

Edit: I misspoke: the evenness-oddness does change for the player!

If player two, on an even turn, blocks two lattice-points, it becomes an even turn for player one. It's a lot like the "picking up the matches" game.

Strategy to guarantee the win when only one lattice-line remains playable:

If even-oddness is in player's favor: play a lattice-point, else play the lattice-line.

share|improve this answer
    
still not sure that this is a complete answer. Even if player 2 can (choose to) change the even-oddness, then player 1 can change it right back? –  Ronald Apr 11 '12 at 22:04
    
@Ronald: a play on a lattice-point blocks three lattice-lines (assuming hex grid,) so opportunities to change even-oddness diminish as the game proceeds. –  Fred Kline Apr 12 '12 at 6:10
    
Misspoke again: up to six lattice-lines will be blocked on one play on a lattice-point. –  Fred Kline Apr 12 '12 at 6:28
    
If the play is in the center of a small triangle, three of each are blocked, parity does not change,and for this reason, I must agree with @TonyK: play anywhere you like. –  Fred Kline Apr 12 '12 at 7:02
    
so, player 2 has no strategy to win, no matter how badly player 1 plays? this seems highly unlikely. –  Ronald Apr 12 '12 at 21:32
show 1 more comment

If you were only allowed to place the pennies on the points of a hexagonal lattice (with the lattice points far enough apart so that pennies can't overlap), then the first player would still win: play opposite the second player, treating the two 'critical points' (the centre of the table, and the point opposite the first move) as opposite.

As Rahul's answer shows, the lattice-point condition is necessary.

Updated to add: After Rudy Toody's answer, I realise that this strategy is overkill. Equally effective is the strategy "play anywhere you like".

share|improve this answer
    
agreed, if you are placing on discrete points. –  Ronald Apr 8 '12 at 12:27
    
Further: if the lattice points are far enough apart so that the pennies don't overlap, then Player 2 can never win (no matter the strategy) because there should be an odd number of points. –  Ronald Apr 11 '12 at 21:21
add comment

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.