7
$\begingroup$

I would like to introduce an ancient African board game I've just invented. Until someone comes up with a better name, it's called Marble Mancala.

Mancala

The rules are pretty simple:

  • There are two players, taking alternating turns. There are 12 numbered bowls, some with a marble in them, some empty.
  • On a turn, the player must take one marble from the board, and
    • optionally, add a new marble to any number of consecutive empty bowls with numbers immediately following the bowl from which the marble was taken.
  • The player to take the last marble wins.

For example, in the picture's position, Take from 2 and add to 3, 4, 5, 6 and 7 would be a legal move, resulting in a total of 6 marbles being on the board. Take from 1 would also be legal in the starting position, but since there are no empty bowls immediately following it (bowl 2 already has a marble), no new marbles could be added, and the other player would immediately win with Take from 2.

You have challenged your friend to this game, and you are starting from the position shown in the picture: one marble in bowls 1 and 2 each, rest of the bowls empty. You have won the coin toss, so you get to choose:

Will you go first, or should you let your opponent start?


The Mancala board base image is from Brooklyn Museum, released under the Creative Commons Attribution 3.0 Unported license. The marble is a free image from Pixabay.


(Not really a) Hint, lifted from the comment section:

You are not supposed to brute-force the game. There is a quite nifty (well, in my opinion, at least) shortcut for figuring out whether it's good to start or not.

$\endgroup$
  • $\begingroup$ ancient board game I've just invented. you're ancient! $\endgroup$ – Omega Krypton Aug 30 at 12:16
  • $\begingroup$ Just in case anyone is wondering, no, you are not supposed to brute-force the game. There is a quite nifty (well, in my opinion, at least) shortcut for figuring out whether it's good to start or not. And yes, at well over 40 years of age, I kinda do feel ancient every now and then. :-) $\endgroup$ – Bass Aug 30 at 12:31
  • $\begingroup$ Do the numbers wrap around? I assume no. $\endgroup$ – hexomino Aug 30 at 12:40
  • $\begingroup$ @hexomino No, they are just plain, regular numbers from 1 to 12. At first glance, such a wrap-around would cause infinitely drawn out games; not being able to add the marble back to the smallest numbered bowl is key in showing that this game is guaranteed to end in a finite time. $\endgroup$ – Bass Aug 30 at 12:51
  • 1
    $\begingroup$ @JaapScherphuis yeah, a checkerboard would have been more useful for explaining the solution too. However, the moves ended up consisting of emptying a bowl and then adding singles to the next couple of bowls, which is pretty much exactly how you play Mancala, so I didn't really have a choice here. (Here are the basic rules of Mancala games, in case someone who hasn't played the game before happens to read this comment.) $\endgroup$ – Bass Sep 1 at 15:03
7
$\begingroup$

You should

Let your opponent start

To prove, let us first do the following

If a bowl contains a marble mark it with a '1', otherwise mark it with a '0'.
Then concatenate the entries in order to form a binary string of length 12.
For example, the starting position in the game above is represented by the string 110000000000.
Now, if we consider this number as a binary number, $s$, representing our state then a single move comprises subtracting a non-negative power of 2 from $s$ (that is, in binary, subtracting a number of the form 1000...000).
So, essentially, this is equivalent to a game of Nim with a single pile of coins where we must remove a non-negative power of 2 from the pile at each step.
There is a simple strategy to winning this game, that is to always leave your opponent with the size of the pile equal to a multiple of 3. This will always be possible as long as the pile your given first is not a multiple of 3 (you can just remove either 1 or 2 coins as required).

Translating this back to our current game, at every step, we must make a move which makes the resulting state, $s$ a multiple of 3. Your opponent's move will then necessarily move the state to not be a multiple of 3 and, in particular, they can never reach 0.

A winning starting configuration is thus determined by whether or not it is a multiple of 3.
If it is not, Player 1 wins. If it is, Player 2 wins.

In this instance $(110000000000)_2 = (11 \times 10000000000)_2$ which is clearly a multiple of 3.
Hence, Player 2 wins with the optimal strategy.

$\endgroup$
  • $\begingroup$ Spot on! By the way, I may have cunningly chosen the starting position so that the base conversion isn't really necessary: dividing away all the factors of 2 (that is, ignoring any trailing zeroes) should instantly give the result. :-) $\endgroup$ – Bass Aug 30 at 14:44
  • $\begingroup$ @Bass, yes, you're right, base conversion is overkill. $\endgroup$ – hexomino Aug 30 at 14:46
3
$\begingroup$

User hexomino already figured out the puzzle, and managed to actually find the very complicated path that was exactly how I came up with the game. To recap:

You can interpret the game position as a binary number (marbles are ones, empty bowls are zeroes). If you do, then every possible move gets exactly mapped, one-to-one, to every possible (binary) subtraction of a non-negative power of two. This reduces the puzzle to another game we have already solved, so we are done.

The game itself is a lot easier to play than that, though, so I'm posting this self-answer to show how.

First, it's very useful to note that in a given board position, every move is uniquely defined by the highest numbered bowl it affects. So instead of saying Take a marble from 2 and add a marble to bowls 3-7 each, we can just say play at 7, and there's going to be exactly one way to do that. Not only is this a nice shorthand way to mark down moves, turns out it's quite crucial in solving the entire puzzle. Below, all moves are given using this notation.

(Now that we've established the notation, you may want to take a peek at the final spoiler block to see the surprisingly simple final conclusion.)

The other, more significant part of the solution is

The balance of marbles in odd and even numbered bowls. Let's call that balance $\Delta$ (Delta). To calculate $\Delta$, simply count the marbles in odd-numbered bowls and subtract the number of marbles in even-numbered bowls.

To see why $\Delta$ so important, let's take a look at how the possible moves affect it:

A play on an odd-numbered bowl with a marble in it removes one odd bowl from the count, so $\Delta$ decreases by one.

A play on an odd-numbered empty bowl, with a marble in the preceding bowl adds one odd bowl, and removes an even bowl, so $\Delta$ increases by two.

A play on an even-numbered bowl with a marble in it removes one even bowl from the count, so $\Delta$ increases by one.

A play on an even-numbered empty bowl, with a marble in the preceding bowl adds one even bowl, and removes an odd bowl, so $\Delta$ decreases by two.

A play on any empty bowl with more empty bowls before it will be equivalent to one of the cases above: if a move affects two adjacent empty bowls, they will cancel each other out, and the remaining highest numbered bowl will have the same parity as the originally played bowl.

Pondering this for a while, we can find these helpful facts:

If we divide $\Delta$ by 3, the remainder will always
* increase by 1, if we play on an odd-numbered bowl.
* decrease by 1, if we play on an even-numbered bowl.

Since we know that the final, winning move leaves a $\Delta$ of exactly zero, and we know that any move either adds one to the remainder $\Delta$ (mod 3), or removes one from it, we can deduce that

* If $\Delta$ is divisible by three, there are no moves that leave $\Delta$ divisible by three, so
* There are no winning moves from a position where $\Delta$ is divisible by three, and
* If $\Delta$ is not divisible by three, there is always a move that leaves a $\Delta$ divisible by three for the opponent.

This gives the winning strategy:

Always play a move that makes $\Delta$ divisible by three.

Using this, we can judge the starting position:

There's one marble in an odd bowl, and one in an even bowl, so $\Delta$ is zero, and it's impossible to play a winning move, so the position is losing.

Therefore, the way to win is to

let the opponent start. Then, whenever the opponent plays on an even-numbered bowl, respond with an odd-numbered bowl (the smallest possible one, if you want the fastest win), and vice versa.

Note that this is exactly the same strategy that @hexomino gives, but instead of doing binary subtraction, decimal conversion and remainder calculations, we are doing the same calculations all in marble binary, which turns out to be quite a lot easier.

$\endgroup$
  • $\begingroup$ can you please explain what is wrong in my answer. $\endgroup$ – Sayed Mohd Ali Sep 2 at 6:42

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.