8
$\begingroup$

In a game of English eight-ball pool, a set of 15 balls are arranged or 'racked' in the shape of an equilateral triangle. In order for the balls to be racked fairly, they must be arranged like so:

A standard rack of balls

......R.....
.....YR.....
.....RBY....
....YRYR....
....RYYRY...

R = Red
Y = Yellow
B = Black

Challenge

As a keen player of the game, I often consider what is the fastest way I could potentially rack a set of balls after dumping them in a random arrangement inside a triangle. I would then attempt to swap one pair of balls at a time until I have a valid rack.

I noticed that depending on how the balls were arranged before sorting, It could be quicker to sort the balls and then finish by rotating the triangle 120° in either direction.

With this in mind, considering every possible combination that the balls could randomly be arranged, what would be the most moves required to create any one of the valid racks as shown below?

Valid Racks

The red and yellow arrangement of balls can be inverted and as the rack is a equilateral triangle it has a rotational symmetry of 3, Therefore there are 6 possible valid solutions:

6 valid racks

In theory, reflecting the pattern would create an equally fair racking arrangement, however it would not be a valid rack within World Rules.

Rules

  • For the purpose of this puzzle, a move is only considered to be the act of swapping any two balls.
  • The act of rotating the entire rack after sorting is not considered a move.

Note

For American pool players the distinction between yellows and reds can be considered the same as 'spots and stripes'.

$\endgroup$
5
  • $\begingroup$ A reflection of the canonical layout isn't fair? $\endgroup$ – msh210 Jan 4 at 22:33
  • $\begingroup$ Your "swapping" link shows two adjacent balls being swapped. Is that all that's allowed, or can any two be? $\endgroup$ – msh210 Jan 4 at 22:34
  • 1
    $\begingroup$ @msh210 In theory, reflecting the pattern would create an equally fair racking arrangement but to keep it simple I am following world rules .Any two balls, they don't have to be adjacent. It's a challenge based on a real life problem, so I am not adding any additional constraints. $\endgroup$ – Ambo100 Jan 4 at 23:09
  • 2
    $\begingroup$ Shouldn't the question be "what would be the most moves required to create any one of the valid racks as shown below?" $\endgroup$ – hexomino Jan 5 at 0:17
  • 1
    $\begingroup$ @hexomino This is a good question and actually one of things I struggled with writing the questions as I wasn't sure which way of phrasing would be clearer, as I assumed it's possible for someone to justify that the most moves would be an almost infinite amount of moves as it's possible to move two balls without ever getting close to solving it. I like the way you have phrased it though so I have updated the question. $\endgroup$ – Ambo100 Jan 5 at 1:22
7
$\begingroup$

This is not a mathematical, but more of a logical approach:

For every possible combination of the balls, there are at most 4 moves required to create one of the valid racks.

The corner positions and the center positions of each edge all together contain six balls from which three are yellow and three are red for every valid rack.
If we place six balls from the same color in these spots (as seen in the image below), there will be three moves required to fix these positions.

enter image description here

Now theres is one red ball left. No matter where it is placed, there will always be a rotation/invertion combination, where the ball is in a correct position. Therefore it does not matter where we place it.

enter image description here

Now if we place the black ball in one of the three center positions, there will also be no move required, to put it into a correct slot. Therefore the black ball has to be placed on one of the edges.

enter image description here

The black ball now leads to the fourth required move.
Now we can fill up the rack with the yellow balls. Their positioning will be fixed by using the correct moves to fix the black and red balls.

One possible combination that requires at least four moves:

enter image description here

$\endgroup$
3
  • $\begingroup$ While this shows that 4 moves are sometimes necessary, it is not clear to me that this proves that there are no arrangements that need 5 or more moves to make it valid. $\endgroup$ – Jaap Scherphuis Jan 5 at 5:32
  • 1
    $\begingroup$ Maybe npkllr consider the at most part as trivial: 1. Swap black to 5th position cost 1 move. 2. At most 3 reds / yellows in [1, 3, 4, 8, 10, 11, 14] position; swap them cost at most 3 moves. $\endgroup$ – tsh Jan 5 at 8:49
  • $\begingroup$ @tsh Fair enough. It is obvious once you see it. Those 7 positions need to be made the same colour, and there are at most 3 balls of the minority colour to be fixed. $\endgroup$ – Jaap Scherphuis Jan 5 at 10:06
1
$\begingroup$

Simpler proof of maximum:

It can be done in at most 4 swaps:
1/ If needed. Move the black to the 'top' middle position
2/ Look how many yellows match the top left setup
3/ If three or less make them all red (in three or less moves) to reach the bottom left position, otherwise make them all yellow to reach the top left position

$\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.