CareerCup

Not sure if I understand the problem correctly, here's what I gather: The game starts with two boxes, each containing different amount (not 0) of chocolates. At each turn a player takes all the chocolates from one of the boxes and divides the chocolates in the other box to two non-equal boxes (in terms of chocolate amount). If at some turn the player cannot select a box and divide the other box into two non-equal sized boxes then this player loses.

The solution to the problem as I described above is as follows:

public static void determineWinner(int c1, int c2){
		if ((c1<=0) || (c2<=0) || (c1==c2)){
			System.out.println("Bad input arguments");
			return;
		}
		
		if ((c1 % 3 == 0) || ((c1>3) && ((c1-2) % 3 ==0)) || 
			(c2 % 3 == 0) || ((c2>3) && ((c2-2) % 3 ==0))){
			System.out.println("Starting player wins.");
		}
		else {
			System.out.println("Starting player loses.");
		}
	}

To see why this solution works, let us define the following:
N - The set of natural numbers (N={1,2,3,...})
L = {1+3k | k in N} union {1,2}
W = N\L = {3k | k in N} union {3k+2 | k in N}

Claim: Given (c1,c2) in N^2 (the boxes) where c1!=c2 and a player x whose turn is the current turn, the following hold:
1. If c1 and c2 are in L then the second player has a winning strategy.
2. If c1 in W or c2 in W then player x has a winning strategy.

Proof: Using induction on n=max{c1,c2}.
Base: To cover the base we can check the following cases:
n=2 : (c1,c2)=(1,2),(2,1). In all these cases no matter which box player x takes, he cannot divide the second box to two non-equal boxes (1 cannot be divided at all and 2 can only be divided to two equal boxes containg one chocolate).
n=3: In this case at least one of the boxes contains 3 chocolates. Player x takes the second box to himself and divides the remaining 3 chocolates to two boxes: (1,2). Using the case of n=2 we deduce that the second player loses no matter what he does and hence player x wins.

Induction step: Assume correctness for every 3<=k<n and let us prove correctness for n=max{c1,c2}. Let us consider the following cases:
1. n in W. There are two possibilities here:

1.1. n = 3m = 3*(m-1) + 3 = (3*(m-1) + 2) + 1. In this case player x takes the box which does not contain n chocolates. He then divides the remaining n chocolates to the following boxes: (3*(m-1)+2,1) which by the induction assumption means that the second player loses.
1.2. n = 3m+2 = 3m+1 + 1. In this case player x takes the box which does not contain n chocolates. He then divides the remaining n chocolates to the following boxes: (3m+1,1) which by the induction assumption means that the second player loses.

2. n in L but the other box contains k>=1 chocolates and k is in W. In this cases we use the same proof as in (1) to show that player x has a winning strategy (just replace n with k).

3. n in L and the other box contains k>=1 chocolates and k is in L as well. For the sake of contradiction, assume that there exist a,b in L such that n = a+b. By the definition of L:

3.1. a = 1 + 3m, b = 1 + 3l where m,l>=1. In this case n = a+b = 1+3m+1+3l=3(l+m)+2 in W which is a contradiction to the fact that n is in L.
3.2. a = 1 + 3m, b = 1. In this case n = a+b = 3m+2 in W and yet again we get a contradiction to the fact that n is in L.
3.3. a = 1 + 3m, b = 2. In this case n = a+b = 3m+3 = 3(m+1) in W which is also a contradiction to the fact that n is in L.
3.4. The other cases are similar and result in a contradiction as well (notice that the case of a=2 and b=2 is not possible).

3.1 - 3.4 show that it is not possible to divide n chocolates to two non-equal boxes with both of them containing a and b chocolates respectively where a and b are in L. The same applies for k (the number of chocolates in the other box) as well. This observation combined with the induction assumption implies that no matter what player x does the second player will win regardless (he has a winning strategy for every move player x makes). Thus, in this case the second player has a winning strategy.

This completes the proof.


An alternative (but expensive) approach can be to use dynamic programming in order to calculate the winner (basically, in each turn the player selects the best move for himself out of all possible moves).