[bonanova]

I thought my last puzzle was more challenging than that,

said Alex after his first swallow of ale at Morty's last night.

You lads have been boning up, it seems.

But that's alright. This one will take a bit longer, I expect,

although it's a child's game. Here; let me show you. At this,

he was joined by Jamie, Ian and Davie at his table.

Look. Each of us starts with a marble. The person who starts

passes a marble to his left. That person then passes two

marbles to his left. That person then passes one marble to

his left, and so on. The number of marbles passed alternates

between one and two.

At any point, if a player has no marbles in front of him he

drops out of the game. And depending on the number of

starting players, one person may end up with all the marbles

to himself. To demonstrate, Alex passed his marble to Jamie,

who passed two marbles to Ian, who passed one marble to

Davey, who passed two marbles to Ian. [Alex and Jamie had

been eliminated after their first pass.] At that point Ian had

all four of the marbles.

Now it might be interesting to figure out which player it will

be that gets all the marbles when it happens, Alex mused,

but we'll leave that thought for another night.

Tonight's question is: for an n-player game, what are the

values of n that will result in one player finally getting all

the marbles? If you understand the problem, you'll find that

n=2, 3, 4, 5 and 6 all terminate with a winner, but the next

terminating number is n=9.

What are the other values of n?

[Glycereine]

Before bed without simulating more than I can in my head, Will have to check it somehow in the morning.

2,3,4,5,6,9,10,17,18,33,34,65,66

where x is any integer (including 0) n = 2^x +1 AND n = 2^x +2

[bonanova]

Before bed without simulating more than I can in my head, Will have to check it somehow in the morning.

2,3,4,5,6,9,10,17,18,33,34,65,66

where x is any integer (including 0) n = 2^x +1 AND n = 2^x +2

Stunned, if not a bit chagrinned at bit at the rapidity of the reply,

Alex nevertheless tips is cap to Glycereine and mutters, alright

then; I suppose a proof is a little much to ask for, so let's move

on to the next issue: who are the winning players?

[Glycereine]

I'll give someone else a chance at the winners . I have a theory though...

[Guest]

tested each one with 4 players-10 players. Found that even number of players had the 3rd guy to the left winning, and the odd number of players had the last guy to the left winning. Does it follow all the way like that?

Is there a formula to find out? I hate math because I know so little , but I like it cause it is fun to learn.

[bonanova]

tested each one with 4 players-10 players. Found that even number of players had the 3rd guy to the left winning, and the odd number of players had the last guy to the left winning. Does it follow all the way like that?

Is there a formula to find out? I hate math because I know so little , but I like it cause it is fun to learn.

Nice result.

There is a known proof for 2+2ⁿ that would verify your first answer.

I don't know the proof for 1+2ⁿ.

I imagine working out the answer for say n=5 would suggest the proof, and the odd answer would follow.

Just a hunch.

[Glycereine]

Nice result.

There is a known proof for 2+2ⁿ that would verify your first answer.

I don't know the proof for 1+2ⁿ.

I imagine working out the answer for say n=5 would suggest the proof, and the odd answer would follow.

Just a hunch.

For the reasoning of both why the values of n that work, do so as well as which player in those values are the winner:

With some quick deduction you can see that no matter how many marbles two players have, 1 of those players will always take 1 marble and give away 2. This makes it so that if any value of n reduces to 2 players remaining, the result will mean there is a winner.

Alternatively if any value of n results in an odd numbers of players remaining (after any complete round) then the solution is no longer solvable (regardless of the number of marbles). This is so because from then on the number of marbles that each player has will vary only by 1, alternating between taking 1 and giving away 2, and taking 2 and giving away 1. Stalemate.

So for any number of working solutions, n must not reduce to an odd number at any time. For this to be the case, the number (after the first round) must always be a multiple of 2. The only way for us to ensure that the number be a multiple of 2 after each round is for us to start backwards from 2 and go up multiplying by 2. This can go on indefinitely, but remember that in the very first round of the game player number 1 will always be eliminated.

Other than player 1, the only players that are eliminated in the first round are the even players.

So if there are an even number of players, then half the players + 1 (number 1 is the plus 1) are gone after round one and the result ((n-2)/2) must be 2^x.

And for an odd number of players the results after round one are a reduction to (n-1)/2 players.

This is why there are two different formulas for values of n.

The two different formulas however 2ⁿ +1 and 2ⁿ +2 have two different winners. This is because adding the extra even number at the end of a working odd "n" still results in a working solution, but moves the winner one player to the right. This is because at the beginning of round 2 instead of starting by giving away 2 marbles, player 3 will start by giving away 1.

In all odd solutions the player that never gives away 2 marbles will be the nth player.

In the even solution, the winner is moved 1 player to the right (discounting even players because they cannot win) to player 3.

so, for a positive integer "x" the following is true:

For 2 players it is obvious player 2 wins.

n = 2^x +1 is a solution, who's winner is n

n = 2^x +2 is a solution, who's winner is 3

That may or may not have helped anyone confused...

Edited June 6, 2009 by Glycereine

[Glycereine]

I should have said "non-negative" integer since 0 is included.

[Guest]

n = 2^x U 2^x + 1, for all x = 1, 2....