All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Pool Ball (Posted on 2005-04-28)
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.

 No Solution Yet Submitted by Juggler Rating: 3.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Seems not to matter | Comment 4 of 15 |

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

 Search: Search body:
Forums (0)