Answer to The Professor's Balls

This is the answer to the puzzle The Professor's Balls.  If you haven't read it yet, here's the link.


Here’s how to work out whether you should take the professor’s bet.

Let (R,G,Y) be current state of the balls' colours expressed as a vector, where R = the number of red balls, G the number of green balls and Y the number of yellow balls. 
Our starting state is therefore 

(13,15,17).

There are three combinations of outcomes from balls hitting each other:
(-1, -1, 2)
(-1, 2, -1)
(2, -1, -1)

Each of these can be applied to the current state to produce a new state.  This would denote a shot where balls hit each other and change colour.  

Here’s the trick


We need to apply mod 3 all of the vectors we’re about to use.  I’ll go in to why below, but here’s what happens if we do that.
Firstly, our Initial State: 

(13, 15, 17) = (1, 0, 2)  (mod 3).

Also, here’s what happens to our three change vectors form above:
(-1, -1, 2) = (2,2,2)

(-1, 2, -1) = (2,2,2)
(2, -1, -1) = (2,2,2)


And so are all equivalent to each other.
So taking our initial vector (1,0,2) and applying any of the three possible changes will mean it will always turn in to (0,2,1).
Also notice that if we apply (2,2,2) to the result, then apply it again, then apply it again, we go full circle.  That is:
(1, 0, 2) + (2, 2, 2) = (0, 2, 1) 

(0, 2, 1) + (2, 2, 2) = (2, 1, 0)
(2, 1, 0) + (2, 2, 2) = (1, 0, 2)


Or, put another way:
(1, 0, 2) -> (0, 2, 1) -> (2, 1, 0) -> (1, 0, 2)

What does this tell us?  It tells us that under the rules of the game, if we have an initial vector and we apply any collision to it three times, we get back to that initial vector.  Its cyclic.

Therefore, if we want to know if we can get from an initial vector to an end vector, all we have to do is apply mod three to that end vector.  It its in that list of three then we’ll be able to get to it.  If its not, then it’s impossible.
Back to our wager then.
So we want to go from (13,15,17) to having all the balls as a single colour.  That is, to one of 
(45,0,0), (0,45,0) or (0,0,45).
Let’s apply our rules to it.
(13,15,17) = (1,0,2) (mod 3)

Given that this is our starting position, the only states that we can possibly end up in are:
(1, 0, 2), (0, 2, 1) and (2, 1, 0)


So let’s see if we can get to the desired end state:
(45,0,0) = (0,0,0) (mod 3)

(0,45,0)=(0,0,0) (mod 3)
(0,0,45)=(0,0,0) (mod 3)


Therefore, since (0,0,0) is not in the set of possible states, being (1, 0, 2), (0, 2, 1) and (2, 1, 0), we can conclude that its impossible to go from the initial state to that desired end state.

QED

Comments

Popular posts from this blog

Is this the Hardest Logic Puzzle in the World?