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.)

this problem could be thought of like this:
let's define a "center of gravity" for the toothpaste:
let's assume X1,X2,X3,X4,X5 is the amount of toothpase in zones 1,2,3,4,5 accordingly (When zone 5 is the outside of the tube).
now we'll define the center of gravity by:
c = 1*X1 + 2*X2 + 3*X3 + 4*X4 + 5*X5

when we are done, and 99% of the toothpaste is out of the tube:

c >= 5 * X5 = 5*99.

now note that when we press any of the zones 2,3,4 - the value of c does NOT change, because, for example, if we press zone 2:

1 * x1 + 2 * x2 + 3 * x3 = 1 * x1 + 0.5 * 1 * x2 + 0.5 * 3 * x2 + 3 * x3

(because for all n: n = 0.5*(n-1) + 0.5(n+1)).

so we can see that we can only increase the center of gravity by pressing zone number one, and we increase it by the value of X1. so now we can look at the problem differently: use as few squeezes as possible to increase the sigma of toothpase squeezed on zone1.

Posted by ronen on 2004-02-21 05:36:18