Impossible search algorithm interview question

Question

How would you solve this question?

You start with a box containing a quantity x of red marbles, y of green marbles and z blue marbles, as well as an unlimited supply of red, green and blue marbles outside the box. One move consists of choosing two different colours, removing two marbles from the box (one of each of your two chosen colours), and then adding a marble of the third colour to the box from your supply. For example, if you choose the colours red and green, then you remove a red and a green marble, and put back a blue one. For what starting conditions (expressed as constraints on x, y, z) can you get exactly one marble in the box by performing zero or more moves?

Answer 1

Working backwards...

From {0,0,1} we can get to {0,1,k} for any k >= 0 by repeatedly picking the 1 to decrement.

From {0,1,k}, k>=1, we can get to {2x,1,k) by alternating between the k and the 1 to decrement.

From {2x,1,k}, k>=1, we can get to {2x,2y+1,k) by alternating between the 2x and the k to decrement.

Thus, any trio which has at least one even, at least one odd, and at least 2 above zero is reachable from a single marble in the inverse.

Answer 2

To explain the parity issue TotallyNoob revealed, we can think about the state as a partition of a sum into three parts. At each stage, the sum is reduced by 1 (-2 + 1), which means the parity of the sum flips. For an odd number, there would be two ways to represent it as a sum of three (odd + odd + odd) or (even + even + odd), and for an even number there would also be two ways, (odd + odd + even) or (even + even + even).

We also know that at each step, all three of the parts flip parity since two are decremented and one incremented. So either we're going between (odd, odd, odd) and (even, even, even) or we're moving between (odd, odd, even) and (even, even, odd). Since we know that the final state is (even, even, odd), we know the state changes must be between (odd, odd, even) and (even, even, odd).

But is this sufficient to know that any starting values (except the obvious {x, 0, 0}, x > 1) would work?

Answer 3

It will converge to one if:

1) Out of three (x, y, z) only two of them are even or odd. i.e. All three of them can't be even or odd, one has to be different.

Any of them can be even or odd there is no constraint on color.

Edit: As pointed out by @onelyner initially, (3, 0, 0) won't work despite following the first rule. Generalizing,

2) Any two of the (x, y, z) can't be zero initially if third is NOT EQUAL to one.

i.e. it must not look like (0, 0, n) where n is not equal to 1.

Something to note here is that we can reach (3, 0, 0) from (2, 1, 1), which should converge to one because it follows both the rules. And if done properly, it surely does converge to one

(2, 1, 1) -> (1, 2, 0) -> (0, 1, 1) -> (1, 0, 0)