When it's time to squeeze out toothpaste, one method is to press down on one particular "zone" of the toothpaste tube. This way, half of the toothpaste will squirt in each direction except for the zone at the end of the tube. When toothpaste squirts out the zone at the front of the tube, it comes out onto your toothbrush.

The problem is a person who uses this toothpaste-squeezing method has to go in for a dentist visit tomorrow, and he haven't even opened his tube of toothpaste. He figure if he can get 99% of the toothpaste on his toothbrush and brush with it, he will have shiny teeth. It's late at night and he doesn't want to have to squeeze the toothpaste tube more than neccesary.

A) What would be the best squeezing strategy if the tube had 3 zones? 4 zones?

B) Is there a best strategy that could apply for any number of zones?

Example:

Toothpaste tube-> |4321=

1/4, 1/4, 1/4, 1/4, (  0 OUT) Press 3:
3/8,    , 3/8, 1/4, (  0 OUT) Press 1:
3/8,    , 1/2,    , (1/8 OUT) Press 2:
3/8, 1/4,    , 1/4, (1/8 OUT) Press 4:
   , 5/8,    , 1/4, (1/8 OUT)

(Assume any part of the tube can have any amount of toothpaste in it, you can only push in the middle of a zone, and the person will not get sick from toothpaste intake.)

The best strategy always seems generally to start with the highest numbered zone (the one farthest from the opening), then the adjacent one, all the way down to the opening, and then start from the highest numbered one again.

The following program finds the sequence for maximizing a given number of squeezes for a given number of zones:
DEFDBL A-Z
DECLARE SUB squeeze (turn)
CLEAR , , 4000
DIM SHARED numZones, maxPushes
numZones = 3: maxPushes = 22
DIM SHARED hPushes(22)
DIM SHARED hContents(22, 4)
DIM SHARED bestPushes(22)
DIM SHARED bestContents(22, 4)

FOR i = 1 TO numZones
 hContents(0, i) = 1 / numZones
NEXT

squeeze 1

FOR t = 1 TO maxPushes
  PRINT bestPushes(t),
  FOR i = numZones TO 0 STEP -1
    PRINT bestContents(t, i);
  NEXT
  PRINT
NEXT

SUB squeeze (turn)
 FOR i = 1 TO numZones
  IF hContents(turn - 1, i) > 0 THEN
   FOR j = 0 TO numZones
    hContents(turn, j) = hContents(turn - 1, j)
   NEXT
   hPushes(turn) = i
   IF i = numZones THEN
     hContents(turn, i - 1) = hContents(turn, i - 1) + hContents(turn, i)
   ELSE
     hContents(turn, i - 1) = hContents(turn, i - 1) + hContents(turn, i) / 2
     hContents(turn, i + 1) = hContents(turn, i + 1) + hContents(turn, i) / 2
   END IF
   hContents(turn, i) = 0
   IF turn = maxPushes THEN
    IF hContents(turn, 0) > bestContents(turn, 0) THEN
     FOR k = 1 TO maxPushes
      PRINT hPushes(k),
      FOR j = 0 TO numZones
       bestContents(k, j) = hContents(k, j)
       PRINT bestContents(k, j);
      NEXT
      PRINT
      bestPushes(k) = hPushes(k)
     NEXT
     PRINT
    END IF
   ELSE
     squeeze turn + 1
   END IF
  END IF
 NEXT
END SUB

By changing numZones and maxPushes a pattern emerges. For any allotted number of squeezes that's a multiple of the number of zones, the best sequence (the one getting the most toothpaste out the end) is of the variety 432143214321.... When the number of allotted squeezes is other than a multiple of the number of zones, there can be a partial sequence somewhere in the middle, such as for example, the most toothpaste that can be squeezed out of a 4-zone tube in 18 squeezes is .58154296875 of the contents, by squeezing 321432432143214321. Note the two partial sequences at the beginning. Another example: for 17 allowed squeezes, the most is .5624, squeezed out by the sequence 43214321343214321, with an extra 3 thrown in the middle.

I don't know if there's any theory behind the extras thrown in among the 4321 subsequences.

If, however, one just starts with 4321... for the 4-zone tube, and continues on that way, for the 4-zone tube, it takes 116 squeezes before over 99% of the tube content has been expelled, 99.135% to be somewhat more exact. If, however, any zone other than 4 is pressed before the beginning of the 4321... repeating sequence, the total number of squeezes, including that initial squeeze, is reduced to 113, though with not quite as much over 99% being expelled. A prepress of zone 1 produces 99.009% after the 113th squeeze; zone 2 or zone 3 produces 99.013%. There's no way of doing it in 112 presses, as the best that can be done with 112 presses is presumably the straight repetition of 4321... as 112 is a multiple of 4, and 112 presses there expels only 98.987%.

For 3 zones, 48 presses using the sequence 321321... expels 99.109% of the toothpaste. Starting with a different zone doesn't seem to help this case.

The program this tries these possibilities is:
DECLARE SUB squeeze (z#)
DEFDBL A-Z
CLEAR , , 4000
DIM SHARED numZones
numZones = 3
DIM SHARED contents(numZones)

CLS
FOR i = 1 TO numZones
 contents(i) = 1 / numZones
NEXT

  tries = 1
  zone = 2
  squeeze zone
  tries = 2
  zone = 1
  squeeze zone
DO
  FOR zone = numZones TO 1 STEP -1
    tries = tries + 1
    PRINT USING "### # "; tries; zone;
    squeeze zone
    IF contents(0) >= .99 THEN EXIT DO
  NEXT
LOOP
END

SUB squeeze (z)
 IF z = numZones THEN
  contents(z - 1) = contents(z) + contents(z - 1)
 ELSE
  contents(z - 1) = contents(z - 1) + contents(z) / 2
  contents(z + 1) = contents(z + 1) + contents(z) / 2
 END IF
 contents(z) = 0
 FOR i = numZones TO 0 STEP -1
   PRINT USING " #.##########"; contents(i);
 NEXT
 PRINT
END SUB



Edited on February 16, 2004, 3:28 pm

Posted by Charlie on 2004-02-16 15:25:16