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 toothpastesqueezing 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 AZ
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 4zone 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 4zone tube, and continues on that way, for the 4zone 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 AZ
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 20040216 15:25:16 