A Puzzle Question

Post Reply New Topic

By English puzzle compiler Henry Dudeney...

There are two people (call them Adam and Bill) on a beach. There are 15 stones on the ground between them. They each take it in turn to pick up some stones. On each turn they can choose to pick up either one, two or three stones. Once all the stones have been picked up, the person who is left holding an odd number of stones wins the game. Adam goes first. Who should win?
(I know the answer.)

An extension to the puzzle (by Dudeney)

What if you start with 13 pebbles on the ground?
(I know the answer.)

Further extensions (by Me)

What about a game where the person left holding an even number of stones wins?
What about a game where the players can choose between picking up 1,2,3 or 4 stones?
If x is the maximum number of stones a player can pick up in one go and y is the number of stones on the ground at the start, can we make a generalisation about the game?
(I haven't looked into these yet.)

Adam wins. There'll always be an odd number of stones.

How do you mean?
Are you saying that Adam will win regardless of whether we start with 15 or 13 stones in the middle?
Note that I am talking about the total number of stones each player is holding at the end of the game (eg, in the game with 15 stones, if one person has 7 stones at the end of the game, the other person has 8.)

Adam starts with 1 stone, he'll keep picking them up until none are left.
He's left with an odd number.

Maybe I did not explain the rules of the game very well.

If Adam starts the game by picking up one stone, it is then Bill's go.

So you could have a game (starting with 15 stones in the middle) where Adam picks up 1, then Bill picks up 1, then Adam picks up 2, then Bill picks up 2, then Adam picks up 3, then Bill picks up 3, then Adam picks up 2, then Bill picks up 1, and then there are none left on the ground and the game ends. In this case then Bill wins the game, because he finishes holding 7 stones and Adam finishes holding 8.

So it is possible for Adam to lose. But is there a way he can guarantee he wins?

Adam wins.

Say there were merely five stones, at the start. Could you explain Adam's winning strategy in that case?

I don't think there is a winning strategy for the person picking first (with 5 stones). It would go like this:

Person A takes 1 stone.
Person B takes 3 stones.
Person A takes last stone.
Person B wins.

or

Person A takes 2 stones.
Person B takes last 3 stones.
Person B wins.

or

Person A takes 3 stones.
Person B takes 1 stone.
Person A takes last stone.
Person B wins.

The OP gave us a hint - 13 is an identical case to 5. If it's your pick at 13, you always will lose. So with the case of 15:

Person A takes 2 stones. (13 left)
Person B takes X stones. (13 - X left)
Person A takes 4-X stones (9 left)
Person B takes Y stones. (9 - Y left)
Person A takes 4-Y stones (5 left)

At this point, both persons have either odd numbers or even numbers. With even numbers, the progression is as above. With odd numbers:

Person B takes 1 stone (even)
Person A takes 2 stones (still odd)
Person B takes 2 stones (still even)
Person A wins

or

Person B takes 2 stones (still odd)
Person A takes 2 stones (still odd)
Person B takes 1 stone (even)
Person A wins

or

Person B takes 3 stones (even)
Person A takes 2 stones (still odd)
Person A wins

I don't think this is quite right.
If it is B's go, and there are 5 stones in the middle, and both players already have an odd number of stones, B can guarantee he will win by taking 1 stone (as he does in the first line of your scenario above). Because:

(i)
If A then takes 1 stone (even)
B then takes 3 stones (odd) and B wins.
(ii)
If A instead takes 2 stones (odd)
B then takes 1 stone (odd)
And A must then take 1 stone (even), and so B wins
(iii)
If A instead takes 3 stones (even)
B then takes 1 stone (odd) and B wins

Characterise all possible game positions for player A by G(a,b,y).
"a" is the number of stones A currently holds, modulo 2.
"b" is the number of stones B currently holds, modulo 2.
"y" is the number of stones remaining.
For a meaningful game, we have a+b+y=1 mod 2, i.e. there are a net odd number of stones.
G(a,b,r) is zero if A cannot win (against ideal player B strategy) and is one if A has a winning strategy from this position.

Let's also say that each player must take from 1 to x stones at their move. (Actually, you could generalise this condition, as well, but not in any particularly neat way that I can see.)

Obviously:
G(0,1,0) = 0
G(1,0,0) = 1

You can easily fill in the rest of the array.

QED.

You're right - I messed that one up. With 5 stones left, the person choosing first wins if they have an odd number of stones already and loses if they have an even number.

I suppose the trick is to find the opposite situation- to find where you always win if you have an even number (0).

... and... without doing anything with my brain... it seems that...

If the number of stones that may be picked up at any turn (y) is up to an EVEN number, then A cannot win when the total number of stones is one less than a multiple of that number plus two (k(y+2)-1).

If the number of stones that may be picked up at any turn (y) is up to an ODD number, then A cannot win when the total number of stones is one less than an odd multiple of that number plus one ((2k+1)(y+1)-1).

E.g. for thirteen (or five) stones with a maximum pick up of three, A should not win, but with fifteen (or eleven, nine or seven) stones to start with, he can.

(The above may all be completely wrong. )