You have five different jugs, without any marks at all, with capacities of 3, 4, 5, 6 and 7 litres. Initially, the 3, 5 and 7-jugs are completely filled with liquid (so we have 15 litres of the liquid; in the diagram below, an "x" stands for 1 litre) and the other two are empty. The jugs are arranged in the circular manner shown below, which can't be changed:

                           | |
                         +-+ +-+
                         | o o |
                         | o o | 
                         +-----+
              | |                        | | 
            +-+ +-+                  +---+ +---+
            |  x  |                  | x x x x |
            | x x |                  |  x x x  |
            +-----+                  +---------+

                   | |           | |                   
                +--+ +--+     +--+ +--+
                | x x x |     | o o o |
                |  x x  |     | o o o |
                +-------+     +-------+

The goal is to achieve 3 litres in each of the 5 jugs, only by pouring liquid from one jug into an adjacent one. (That is, at any time, you can pour liquid from the 3-jug only into the 4-jug or to the 5-jug; or from the 7-jug only into the 4-jug or to the 6-jug, etc...)

(In reply to symetrical bottles by Sir Percivale)

The hypothesis also assumes that the capacity includes the use of the neck of the bottle as part of the storage, so the capacity is reached only when filled to the actual rim.  Also, since pourings take place, one must replace (or initially place) that foil top when needed.  The caveat also is that the jug must be full at the given stage when this is used.

But to answer your question, only 5 steps are needed if it's possible to pour half the contents:

     3    0    7    0    5  
     0    3    7    0    5
     3    3    7    0    2
     3    3    7    2    0
     3    3    3    6    0
     3    3    3    3    3

The half rule was applied only in the last step.

The program, with the half rule feature in bold:

DECLARE SUB try (lvl!)
DIM SHARED amt(3 TO 7)
DIM SHARED hist(15, 3 TO 7), ansCt, best

OPEN "fivejug2.txt" FOR OUTPUT AS #2

amt(3) = 3
amt(5) = 5
amt(7) = 7
best = 999

try 1

CLOSE

END

SUB try (lvl)
 good = 1
 FOR jug = 3 TO 7
  hist(lvl, jug) = amt(jug)
  IF amt(jug) <> 3 THEN good = 0
 NEXT
 IF good THEN
   ansCt = ansCt + 1
   IF lvl < best THEN best = lvl
   FOR i = 1 TO lvl
     FOR j = 3 TO 7
      j2 = j
      IF j = 5 THEN j2 = 7
      IF j = 7 THEN j2 = 5
       PRINT TAB((j - 2) * 5); hist(i, j2);
       PRINT #2, TAB((j - 2) * 5); hist(i, j2);
     NEXT
     IF i = 1 THEN
      PRINT ansCt, lvl, best
      PRINT #2, ansCt, lvl
     ELSE
       PRINT
       PRINT #2,
     END IF
   NEXT
   PRINT
   PRINT #2,
 ELSE
  IF lvl < 6 THEN
   FOR j1 = 3 TO 7
     IF j1 < 7 THEN j2 = j1 + 1:  ELSE j2 = 4
     IF j1 = 4 THEN j2 = 7
     IF amt(j1) > 0 AND amt(j2) < j2 THEN
       IF amt(j1) > j2 - amt(j2) THEN
        trfr = j2 - amt(j2)
       ELSE
        trfr = amt(j1)
       END IF
       amt(j2) = amt(j2) + trfr
       amt(j1) = amt(j1) - trfr
       try lvl + 1
       amt(j2) = amt(j2) - trfr
       amt(j1) = amt(j1) + trfr
       IF amt(j1) = j1 AND j1 / 2 < j2 - amt(j2) THEN
         amt(j2) = amt(j2) + j1 / 2
         amt(j1) = amt(j1) - j1 / 2
         try lvl + 1
         amt(j2) = amt(j2) - j1 / 2
         amt(j1) = amt(j1) + j1 / 2
       END IF
     END IF
     IF j1 > 3 THEN j2 = j1 - 1:  ELSE j2 = 5
     IF j1 = 5 THEN j2 = 3
     IF amt(j1) > 0 AND amt(j2) < j2 THEN
       IF amt(j1) > j2 - amt(j2) THEN
        trfr = j2 - amt(j2)
       ELSE
        trfr = amt(j1)
       END IF
       amt(j2) = amt(j2) + trfr
       amt(j1) = amt(j1) - trfr
       try lvl + 1
       amt(j2) = amt(j2) - trfr
       amt(j1) = amt(j1) + trfr
       IF amt(j1) = j1 AND j1 / 2 < j2 - amt(j2) THEN
         amt(j2) = amt(j2) + j1 / 2
         amt(j1) = amt(j1) - j1 / 2
         try lvl + 1
         amt(j2) = amt(j2) - j1 / 2
         amt(j1) = amt(j1) + j1 / 2
       END IF
     END IF
   NEXT
  END IF
 END IF
END SUB

 

Posted by Charlie on 2005-08-19 14:59:59