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:
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