Well,

I know that even this time the title does not give any clue what the post is about, but well, at least it looks cool, eh? Just like ‘Matrix Reloaded’. Anyways, let’s get to the point.

Problem : I would like to give credit for this puzzle to Manoj and Sameer. Okay, so the problem goes as follows. There are two boxes A and B with m balls in one box and n balls in another. What you can do is take out any number of balls from any one of the box or you can take out equal number of balls from both the boxes. For example, you can take out 4 balls from A or 7 balls from B or 3 balls from both A and B. Of course you have an opponent in this game. At the end both A and B will be empty. The last person to make the move wins.

If you have the first move to make, what will be your stretagy? One thing is for sure that you can not always win. For example in a configuration (1,2) it is impossible for you to win no matter what move you make. In a sense (1,2) is a loosing state. Your job is to find out whether given configuration is a winning state or not and if it is a winning state, what will be the sequence of moves that will lead you to victory.

Yeah, I know it is one of those bunch of puzzles where you have to play a game with opponent and the last person to make the move wins or looses. Long back I posted a very interesting puzzle on a different blog.

Solution : Normally, the way to tackle this kind of puzzle is to build a state transition graph where sequence of transition alterntes between a winning state and loosing state. So idea thing would be to make a move so that the opponent always end up in loosing state.

I tried this approach first but unfortunately could not exhaust all the cases. For simplicity, I will only describe bases where in any state m < n because of symmetry of the problem. L denotes a loosing state and W denotes a winning state. Here, the state is independent of the player. Whosoever ends up in a winning state can win and similarly he/she can loose if loosing state is encountered.

(0,0)L <– (0,i)W <– (i,i)W

<– (i,i)W <– (j,j)W

(i,i+1)W ( except (1,2) )

(i,i+2)W ( except (2,4) (3,5) )

You can see that you can build a list of winning states with a list of exceptions where you can loose. Basically, I could not find any close form function in terms of (m,n) from which I can determine in constant time whether I can win or not.

The trick Sameer mentioned takes O(m) time.

We know that for |m-n| = 1, (1,2) is a loosing state. That also  makes (1,>2) and (2,>1) winning states. For |m-n| = 2, there is (3,5) making (3,>5) and (5,>3) winning states. Next possible number which is unused is 4 so (4,7) is the loosing state for |m-n| = 3. (6,10) will be loosing state for |m-n|=4.

One can construct such loosing state for any given |m-n| in O(m) time and O(m) space in this way. Now the stretagy is the following.

m=n  –> take out (m,m) and you win

m<n –> check whether (m,n) is a loosing state. If it is, you are doomed. If it is not, then there must be a loosing state (m,n’) corresponding to m.

if n’ > n then you will be able to find a loosing state (m”,n”) such that |m” – n” | = | m-n| and m” < m. Take out (m-m”,m-m”) to reduce (m,n) to (m”,n”) and your opponent is doomed.

if n’ < n, then take your move would be (0,n-n’) which will take (m,n) to (m,n’) and the soul of your opponent wll rest in peace.

Let’s take a look what makes a loosing state (m,m+i) a loosing state. We know that all numbers from 0 to m-1 are used to form a winning state. If you take out anything from m you end up in a state (j,m+i). There exist a loosing state (k,j) or (j,k) where |k-j| < i. So in the next move your opponent will take you from (j,m+i) to one of these states and you will be fragged.

If you make a move (l,l) you will end up in (j,j+i) and again your partner will lead you to hell through (j,k) or (k,j) as described above. So the lesser number m must not reduce. The only option remains for you is to move (0,l) where l<i). But that reduces the difference |m-n| < i. Now as described in the winning stretagy your opponent will take out (m-m”,m-m”) which will put an end to your game.

Again, I apologize if these i,j,k,l,m,n bothered you too much. One can take some concrete example and see that it works.

–Saurabh Joshi