Author Topic: The Penny Game (ACOPS)  (Read 4860 times)

0 Members and 1 Guest are viewing this topic.

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2398
    • View Profile
The Penny Game (ACOPS)
« on: May 02, 2008, 10:19:57 PM »
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?

Offline Nate

  • Full Member
  • ***
  • Posts: 425
  • You all suck
    • View Profile
Re: The Penny Game (ACOPS)
« Reply #1 on: May 03, 2008, 05:00:27 AM »
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.


Offline Camel

  • Hero Member
  • *****
  • Posts: 1705
    • View Profile
    • BNU Bot
Re: The Penny Game (ACOPS)
« Reply #2 on: May 06, 2008, 12:54:42 PM »
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.

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

Offline Joe

  • B&
  • x86
  • Hero Member
  • *****
  • Posts: 10326
  • In Soviet Russia, text read you!
    • View Profile
    • Github
Re: The Penny Game (ACOPS)
« Reply #3 on: May 06, 2008, 03:15:19 PM »
Tic-tac-toe, on the other hand, gives a LOT of advantage to the first player.
I'd personally do as Joe suggests

You might be right about that, Joe.


Offline dark_drake

  • Mufasa was 10x the lion Simba was.
  • x86
  • Hero Member
  • *****
  • Posts: 2447
  • Dun dun dun
    • View Profile
Re: The Penny Game (ACOPS)
« Reply #4 on: May 06, 2008, 08:05:20 PM »
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.  :-\
errr... something like that...

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2398
    • View Profile
Re: The Penny Game (ACOPS)
« Reply #5 on: May 08, 2008, 12:24:28 PM »
No one's got it yet. I may post the solution later today or tomorrow.

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2398
    • View Profile
Re: The Penny Game (ACOPS)
« Reply #6 on: May 08, 2008, 04:02:08 PM »
Hint #1: Symmetry.

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2398
    • View Profile
Re: The Penny Game (ACOPS)
« Reply #7 on: May 08, 2008, 04:14:30 PM »
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.

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17928
  • Fnord.
    • View Profile
    • SkullSecurity
Re: The Penny Game (ACOPS)
« Reply #8 on: May 08, 2008, 05:11:56 PM »
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.

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2398
    • View Profile
Re: The Penny Game (ACOPS)
« Reply #9 on: May 08, 2008, 05:36:46 PM »
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.

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17928
  • Fnord.
    • View Profile
    • SkullSecurity
Re: The Penny Game (ACOPS)
« Reply #10 on: May 08, 2008, 06:43:55 PM »
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?

Offline Camel

  • Hero Member
  • *****
  • Posts: 1705
    • View Profile
    • BNU Bot
Re: The Penny Game (ACOPS)
« Reply #11 on: May 08, 2008, 07:28:41 PM »
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.

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2398
    • View Profile
Re: The Penny Game (ACOPS)
« Reply #12 on: May 08, 2008, 07:45:18 PM »
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 =)

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17928
  • Fnord.
    • View Profile
    • SkullSecurity
Re: The Penny Game (ACOPS)
« Reply #13 on: May 08, 2008, 08:08:00 PM »
Yep, good job =)
It was fairly obvious based on your hint, once I realized what the game was about. :P