You have 15 pool balls arranged in a triangle.

What is the greatest number of balls you will ever have to swap in order to ensure that they are all in the correct position at the start of the game?

An allowable position is either the one in the diagram above, the same position mirrored left-to-right, or either of these arrangements with the red and yellow balls switched.

The diagram of a triangle is equivalent to a row of pool balls.  When I change the diagram and the other allowable positions to a row, I get the following:

BRRRRRRRYYYYYYY
BYYYYYYYRRRRRRR
BRRYYYYYRRRRRYY
BYYRRRRRYYYYYRR

The starting row can be any of the possible 15!/(7!7!) permutations, which is 51480.

If the black ball is in the incorrect position, the only thing to do is swap it; there is no way to save moves.  The rest of the balls are now in any of the 14!/(7!7!) (which is 3432) permutations left, and 1 move has been made.

The rest of the moves will consist of switching red balls with yellow balls such that both swapped balls will be in the correct positions.  The number of swaps here will be equal to half the number of balls in the incorrect positions.  I can just as easily say that it is equal to the number of Red balls in the yellow positions.

Just counting the first two rows, it is obvious that no more than 3 moves are required, because if more than 3 red balls are in the yellow position, it is easier to aim for the inverted row.

Even when counting the mirror images, this stays the same, since having seven balls in the middle will always cause at least 3 red balls to be in the yellow positions.

Therefore, 4 moves are needed.

Posted by Tristan on 2005-04-29 16:07:02