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 lefttoright, or either of these arrangements with the red and yellow balls switched.
If only color reversals were allowed, and not leftright mirrorimage 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 colorreversed 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 colorreversed 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 worstcase scenario, the black at the top, then red balls in both positions on the 2ball row, all three positions on the 3ball row and the first two positions on the 4ball row. This requires 4 swaps.

Posted by Charlie
on 20050428 15:14:53 