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

 Total Toothpaste (Posted on 2004-02-16)
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.)

 See The Solution Submitted by Gamer Rating: 4.4000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Heuristic method | Comment 2 of 5 |
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

 Search: Search body:
Forums (1)