4
$\begingroup$

A friend and I were playing some English pool yesterday. When you rack the balls it has the specific set up in the picture where the 8 ball must be in that central position and the balls are laid out either as in the picture OR the opposite way round, i.e. the reds take the yellow's positions.

enter image description here

When you set up the game you generally place all the balls in a triangle and then rearrange them into the correct set up positions. We wondered what would be the least amount of moves it would take to get to the correct set up from a random starting position. We define a move here as swapping the position of two balls.

My thoughts are that the upper bound is 4 moves. In the worst case scenario, you can guarantee at least 6 balls in incorrect positions regardless of whether you choose the set up in the picture or the opposite set up where the reds take the yellow's positions. Two colours must be the same in the two top right positions, so placing one of each colour in those positions guarantees one incorrect placement. Using the same logic for other positions (such as the striped lines in the bottom left) and placing the 8 ball away from the centre, the second picture shows a starting position guaranteeing 6 incorrect balls.

enter image description here

I suspect you can now place the remaining balls arbitrarily and the least number of moves will depend on which colour is in the 8 ball's position. I think that that swap should also determine whether you should choose the set up in the first picture or the opposite set up, but I can't quite formalise this.

Anyway, I thought it was a fun problem if anyone cares to prove or disprove the conjecture!

$\endgroup$
1
$\begingroup$

The geometry plays no role at all.

Consider simply $2n+1$ positions of which one is meant for a B-ball, two sets of $n$ special positions and the goal is to place all Y-balls in one set and all R-balls in the other.

Consider the initial config.

  1. If the B-ball is in its correct position, let one set of positions have $x$ Y-balls, $n-x$ R-balls, the other set has $x$ R-balls, $n-x$ Y-balls.

Then the number of swaps needed is $min(x,n-x)$ which is at most $\lfloor n/2 \rfloor$.

  1. If Y is at B's place, let one set of positions have the B-ball, $x$ Y-balls, $n-x-1$ R-balls, so that the other has $n-x-1$ Y-balls, $x+1$ R-balls.

Now w.l.og. we can first put the B-ball in its place using 1 swap, so the remaining positions have $(x+1,n-x-1)$ and $(n-x-1,x+1)$ resp. In this case, the total number of swaps is at most $1+\lfloor n/2 \rfloor$.

Thus it is clear both how to set up the worst case (choose $x+1=\lfloor n/2 \rfloor$ in Case 2) and that the max # swaps is $1+ \lfloor n/2 \rfloor$.

Now in the OP's configuration, we have (3 R, 3 Y) and (2 R, 2 Y, 1 B). Swapping the B-ball into its correct place will put 3 balls of one color in the second set; let's say this yields (3 R, 3 Y), (3 R, 2 Y). Now there are 3 balls left, of which 1 will go into the first set. If that's R, the 3 R from the second set can be swapped into the first set; if that's yellow, there must be 3 Y in the second set which can be swapped into the first set. So the OP's claim is correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.