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

Home > Games
Pool Ball (Posted on 2005-04-28) Difficulty: 3 of 5
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.)
Solution 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information