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.

If only color reversals were allowed, and not left-right mirror-image solution, one would expect to need at most 4 swaps: 1 to swap the black to it's proper position, and then, depending on whether the original diagram or the color-reversed diagram requires fewer swaps, at most 3 more.  That's because if 4 swaps were required, it could be changed into 3 by the color reversal; 5 could be changed to 2; 6 to 1; and 7 would already be the color-reversed solution.

Adding the mirror image possibility doesn't seem to help this, as indicated by the result of this program:

p$(1) = "rryybrryryyyryr"
p$(2) = "ryrrbyyryrryryy"
FOR i = 1 TO 2
  j = i + 1
  FOR k = 1 TO 15
    IF MID$(p$(i), k, 1) = "r" THEN p$(j) = p$(j) + "y"
    IF MID$(p$(i), k, 1) = "b" THEN p$(j) = p$(j) + "b"
    IF MID$(p$(i), k, 1) = "y" THEN p$(j) = p$(j) + "r"
  NEXT
NEXT i
FOR black = 1 TO 15
 IF black = 1 THEN r1 = 2:  ELSE r1 = 1
 r(1) = r1
 FOR r2 = r1 + 1 TO 11
  IF r2 <> black THEN
  r(2) = r2
  FOR r3 = r2 + 1 TO 12
  IF r3 <> black THEN
  r(3) = r3
  FOR r4 = r3 + 1 TO 13
  IF r4 <> black THEN
  r(4) = r4
  FOR r5 = r4 + 1 TO 14
  IF r5 <> black THEN
  r(5) = r5
  FOR r6 = r5 + 1 TO 15
  IF r6 <> black THEN
   r(6) = r6
  FOR r7 = r5 + 1 TO 15
  IF r7 <> black THEN
   r(7) = r7
   best = 99
   FOR i = 1 TO 4
     t = 0
     IF black <> 5 THEN
      t = 1
      IF r1 = 5 THEN
       r(1) = black
      END IF
      IF r2 = 5 THEN
       r(2) = black
      END IF
      IF r3 = 5 THEN
       r(3) = black
      END IF
      IF r4 = 5 THEN
       r(4) = black
      END IF
      IF r5 = 5 THEN
       r(5) = black
      END IF
      IF r6 = 5 THEN
       r(6) = black
      END IF
      IF r7 = 5 THEN
       r(7) = black
      END IF
     END IF
     FOR j = 1 TO 7
      IF MID$(p$(i), r(j), 1) <> "r" THEN
       t = t + 1
      END IF
     NEXT
     IF t < best THEN best = t: o = i
   NEXT i
   IF best > worst THEN
    worst = best: so = o: sb = black
    sr1 = r1: sr2 = r2: sr3 = r3: sr4 = r4: sr5 = r5: sr6 = r6: sr7 = r7
   END IF
  END IF
  NEXT r7
  END IF
  NEXT r6
  END IF
  NEXT r5
  END IF
  NEXT r4
  END IF
  NEXT r3
  END IF
 NEXT r2
NEXT black
PRINT worst
PRINT sb, sr1; sr2; sr3; sr4; sr5; sr6; sr7, p$(so)

which finds as an example of the worst-case scenario, the black at the top, then red balls in both positions on the 2-ball row, all three positions on the 3-ball row and the first two positions on the 4-ball row. This requires 4 swaps.

Posted by Charlie on 2005-04-28 15:14:53