The Penny Game (ACOPS)

[Ender]

Here's a really cool problem I just did today.

Sidoh and Joe's mom are playing an intense two-player game called The Penny Game. In this game each player takes turns placing a penny on the surface of a rectangular table in a way such that no two pennies on the table touch. Initially there are no pennies on the table, and the last player to make a legal move wins.

Does the first player to move have a winning strategy?

[Nate]

It depends directly on the size of the table.  Both players are trying to minimize so the first to achieve zero available locations to place a penny wins.

[Camel]

The first player has an advantage of the same caliber that white has the advantage in chess: it has no bearing on the outcome of the game if played by any two real humans.

[Joe]

Tic-tac-toe, on the other hand, gives a LOT of advantage to the first player.

[dark_drake]

Tic-tac-toe, on the other hand, gives a LOT of advantage to the first player.

Every game ends in a tie if players play with the best strategy.  :-\

[Ender]

No one's got it yet. I may post the solution later today or tomorrow.

[Ender]

Hint #1: Symmetry.

[Ender]

It depends directly on the size of the table.  Both players are trying to minimize so the first to achieve zero available locations to place a penny wins.

It seems like that at first... ;-) That is why I like this problem so much =)

The first player has an advantage of the same caliber that white has the advantage in chess: it has no bearing on the outcome of the game if played by any two real humans.

This game is not nearly as complicated as chess, and the problem does have a solution.

[iago]

My thought would be to "solve" the problem for a 2x2 table (easy -- put it anywhere), a 3x3 (put it in the middle), a 4x4, 5x5, etc. Hopefully, a pattern will emerge and become a universal strategy.


But, to completely answer your original question:

Does the first player to move have a winning strategy?

Yes.

[Ender]

My thought would be to "solve" the problem for a 2x2 table (easy -- put it anywhere), a 3x3 (put it in the middle), a 4x4, 5x5, etc. Hopefully, a pattern will emerge and become a universal strategy.

Oh? :P

But, to completely answer your original question:

Does the first player to move have a winning strategy?

Yes.

You're right :P But you must prove it. Don't be daunted by the word "prove", though. Think of it as coming up with an argument that no one can deny. The best way to prove it in this case, and in many problems like this, is to come up with an algorithm for winning, i.e. an algorithm (strategy) that guarantees that the first player to move wins.

[iago]

My thought would be to "solve" the problem for a 2x2 table (easy -- put it anywhere), a 3x3 (put it in the middle), a 4x4, 5x5, etc. Hopefully, a pattern will emerge and become a universal strategy.

Oh? :P

Hmm, I was assuming a grid, but now that I re-read the question, I see that there isn't one. :)

But, to completely answer your original question:
Yes.

You're right :P But you must prove it. Don't be daunted by the word "prove", though. Think of it as coming up with an argument that no one can deny. The best way to prove it in this case, and in many problems like this, is to come up with an algorithm for winning, i.e. an algorithm (strategy) that guarantees that the first player to move wins.

You didn't say that! You just asked a yes/no question, and I gave the correct answer based on meta-data. Basically, you wouldn't have asked this if the question was no. :P

But actually, I think based on your hint that I see the answer.

1) Place you first penny in the exact center
2) Place your second, third, etc. penny exactly on the opposite side of the table. By definition, there won't be a penny there.

Eventually, there will be nowhere left to go for player 2.

What do I win?

[Camel]

The first player has an advantage of the same caliber that white has the advantage in chess: it has no bearing on the outcome of the game if played by any two real humans.

This game is not nearly as complicated as chess, and the problem does have a solution.

Given that iago's answer is obviously correct, what I meant by that is humans are fallible, and it would be extremely unlikely for human players to pull off that strategy, for similar reasons to the idea that white has an advantage in chess - where in chess RAM is the issue, and in this game hand/eye coordination is the issue.

[Ender]

My thought would be to "solve" the problem for a 2x2 table (easy -- put it anywhere), a 3x3 (put it in the middle), a 4x4, 5x5, etc. Hopefully, a pattern will emerge and become a universal strategy.

Oh? :P

Hmm, I was assuming a grid, but now that I re-read the question, I see that there isn't one. :)

But, to completely answer your original question:
Yes.

You're right :P But you must prove it. Don't be daunted by the word "prove", though. Think of it as coming up with an argument that no one can deny. The best way to prove it in this case, and in many problems like this, is to come up with an algorithm for winning, i.e. an algorithm (strategy) that guarantees that the first player to move wins.

You didn't say that! You just asked a yes/no question, and I gave the correct answer based on meta-data. Basically, you wouldn't have asked this if the question was no. :P

But actually, I think based on your hint that I see the answer.

1) Place you first penny in the exact center
2) Place your second, third, etc. penny exactly on the opposite side of the table. By definition, there won't be a penny there.

Eventually, there will be nowhere left to go for player 2.

What do I win?

Yep, good job =)

[iago]

Yep, good job =)

It was fairly obvious based on your hint, once I realized what the game was about. :P