2
$\begingroup$

There are n buckets in a line. Each contains a random number of balls.

Two players take turns and pick some number of balls from a bucket. They can move to the next bucket only if the previous one has been emptied. The last person to pick wins the game.

What is the strategy for winning the game.

(I am new to Game Theory and unsure if this is a rephrasing of some standard problem.)

My take is to start first. -Take all the balls out if odd number of buckets are remaining. -Take all but one ball if even buckets are remaining.

$\endgroup$
0
$\begingroup$

You are thinking in the right direction, but what happens if there are an even number of remaining buckets and the one you have to pick from starts with only one ball? A small tweak to your strategy will fix the problem.

Added: Note that your strategy has the same player (you) playing first in each bucket. You do that by ensuring that each bucket takes two turns to empty. As long as there is more than one ball in each bucket to start it works fine. A bucket with a single ball only permits one turn, so ruins your strategy. You want to start if there are no buckets with a single ball. If there is one bucket with a single ball, you want to start the bucket just after it, so you want your opponent to take the single ball. That means you want to start the bucket just before the single ball so you can empty it in one turn. You don't want to finish the bucket two before the single ball because then your opponent wins. As long as there are not two single ball buckets in a row, you win by taking all but one ball unless the bucket is just before a single, in which case you take them all. If there are two single ball buckets in a row, they cancel out because each will take exactly one turn and you can ignore them.

$\endgroup$
  • $\begingroup$ In that case. I can either choose to not go first. Or choose to pick zero number of balls (game won't end but I won't lose) $\endgroup$ – fzn Nov 19 '17 at 4:11
  • $\begingroup$ Usually picking zero is not an option. If you don't want to pick zero neither does your opponent, so if that is an option the game will never end. As your strategy leaves a single ball you will get stuck unless the player is required to take at least one ball. The improvement needs to be a little more subtle because the bin with one ball could be a ways down the line. $\endgroup$ – Ross Millikan Nov 19 '17 at 4:35
  • $\begingroup$ There also could be more than one bin with only one ball at the start. $\endgroup$ – Ross Millikan Nov 19 '17 at 5:26
  • $\begingroup$ Base strategy is to ensure opponent picks last ball in each bucket, to have the player pick first in each bucket. This can be done by starting first. For cases where there are bucket of 1 balls, player needs to ensure he gets to pick first in the next bucket with more than 1 balls (or the last bucket). For instance {.., 2, 1, n} player picks all balls from the 2 ball bucket. {.., 2, 1, 1, n} player leaves one ball in the 2 balls bucket. I couldn't write the strategy properly, but this wins all games. $\endgroup$ – fzn Nov 19 '17 at 5:38
  • $\begingroup$ Slight addition.. if 1st bucket had 1 ball, player need not start first. $\endgroup$ – fzn Nov 19 '17 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.