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 following shows the zone contents and amount already expelled for the best 4-zone case. Zone 4 is farthest from the opening and zone 1 nearest.

s# zone  zone 4     zone 3     zone 2      zone 1  total on brush


 1 2  0.25000000 0.37500000 0.00000000 0.37500000 0.00000000


 2 4  0.00000000 0.62500000 0.00000000 0.37500000 0.00000000


 3 3  0.31250000 0.00000000 0.31250000 0.37500000 0.00000000


 4 2  0.31250000 0.15625000 0.00000000 0.53125000 0.00000000


 5 1  0.31250000 0.15625000 0.26562500 0.00000000 0.26562500


 6 4  0.00000000 0.46875000 0.26562500 0.00000000 0.26562500


 7 3  0.23437500 0.00000000 0.50000000 0.00000000 0.26562500


 8 2  0.23437500 0.25000000 0.00000000 0.25000000 0.26562500


 9 1  0.23437500 0.25000000 0.12500000 0.00000000 0.39062500


10 4  0.00000000 0.48437500 0.12500000 0.00000000 0.39062500


11 3  0.24218750 0.00000000 0.36718750 0.00000000 0.39062500


12 2  0.24218750 0.18359375 0.00000000 0.18359375 0.39062500


13 1  0.24218750 0.18359375 0.09179688 0.00000000 0.48242188


14 4  0.00000000 0.42578125 0.09179688 0.00000000 0.48242188


15 3  0.21289063 0.00000000 0.30468750 0.00000000 0.48242188


16 2  0.21289063 0.15234375 0.00000000 0.15234375 0.48242188


17 1  0.21289063 0.15234375 0.07617188 0.00000000 0.55859375


18 4  0.00000000 0.36523438 0.07617188 0.00000000 0.55859375


19 3  0.18261719 0.00000000 0.25878906 0.00000000 0.55859375


20 2  0.18261719 0.12939453 0.00000000 0.12939453 0.55859375


21 1  0.18261719 0.12939453 0.06469727 0.00000000 0.62329102


22 4  0.00000000 0.31201172 0.06469727 0.00000000 0.62329102


23 3  0.15600586 0.00000000 0.22070313 0.00000000 0.62329102


24 2  0.15600586 0.11035156 0.00000000 0.11035156 0.62329102


25 1  0.15600586 0.11035156 0.05517578 0.00000000 0.67846680


26 4  0.00000000 0.26635742 0.05517578 0.00000000 0.67846680


27 3  0.13317871 0.00000000 0.18835449 0.00000000 0.67846680


28 2  0.13317871 0.09417725 0.00000000 0.09417725 0.67846680


29 1  0.13317871 0.09417725 0.04708862 0.00000000 0.72555542


30 4  0.00000000 0.22735596 0.04708862 0.00000000 0.72555542


31 3  0.11367798 0.00000000 0.16076660 0.00000000 0.72555542


32 2  0.11367798 0.08038330 0.00000000 0.08038330 0.72555542


33 1  0.11367798 0.08038330 0.04019165 0.00000000 0.76574707


34 4  0.00000000 0.19406128 0.04019165 0.00000000 0.76574707


35 3  0.09703064 0.00000000 0.13722229 0.00000000 0.76574707


36 2  0.09703064 0.06861115 0.00000000 0.06861115 0.76574707


37 1  0.09703064 0.06861115 0.03430557 0.00000000 0.80005264


38 4  0.00000000 0.16564178 0.03430557 0.00000000 0.80005264


39 3  0.08282089 0.00000000 0.11712646 0.00000000 0.80005264


40 2  0.08282089 0.05856323 0.00000000 0.05856323 0.80005264


41 1  0.08282089 0.05856323 0.02928162 0.00000000 0.82933426


42 4  0.00000000 0.14138412 0.02928162 0.00000000 0.82933426


43 3  0.07069206 0.00000000 0.09997368 0.00000000 0.82933426


44 2  0.07069206 0.04998684 0.00000000 0.04998684 0.82933426


45 1  0.07069206 0.04998684 0.02499342 0.00000000 0.85432768


46 4  0.00000000 0.12067890 0.02499342 0.00000000 0.85432768


47 3  0.06033945 0.00000000 0.08533287 0.00000000 0.85432768


48 2  0.06033945 0.04266644 0.00000000 0.04266644 0.85432768


49 1  0.06033945 0.04266644 0.02133322 0.00000000 0.87566090


50 4  0.00000000 0.10300589 0.02133322 0.00000000 0.87566090


51 3  0.05150294 0.00000000 0.07283616 0.00000000 0.87566090


52 2  0.05150294 0.03641808 0.00000000 0.03641808 0.87566090


53 1  0.05150294 0.03641808 0.01820904 0.00000000 0.89386994


54 4  0.00000000 0.08792102 0.01820904 0.00000000 0.89386994


55 3  0.04396051 0.00000000 0.06216955 0.00000000 0.89386994


56 2  0.04396051 0.03108478 0.00000000 0.03108478 0.89386994


57 1  0.04396051 0.03108478 0.01554239 0.00000000 0.90941232


58 4  0.00000000 0.07504529 0.01554239 0.00000000 0.90941232


59 3  0.03752264 0.00000000 0.05306503 0.00000000 0.90941232


60 2  0.03752264 0.02653252 0.00000000 0.02653252 0.90941232


61 1  0.03752264 0.02653252 0.01326626 0.00000000 0.92267858


62 4  0.00000000 0.06405516 0.01326626 0.00000000 0.92267858


63 3  0.03202758 0.00000000 0.04529384 0.00000000 0.92267858


64 2  0.03202758 0.02264692 0.00000000 0.02264692 0.92267858


65 1  0.03202758 0.02264692 0.01132346 0.00000000 0.93400204


66 4  0.00000000 0.05467450 0.01132346 0.00000000 0.93400204


67 3  0.02733725 0.00000000 0.03866071 0.00000000 0.93400204


68 2  0.02733725 0.01933035 0.00000000 0.01933035 0.93400204


69 1  0.02733725 0.01933035 0.00966518 0.00000000 0.94366722


70 4  0.00000000 0.04666760 0.00966518 0.00000000 0.94366722


71 3  0.02333380 0.00000000 0.03299898 0.00000000 0.94366722


72 2  0.02333380 0.01649949 0.00000000 0.01649949 0.94366722


73 1  0.02333380 0.01649949 0.00824974 0.00000000 0.95191696


74 4  0.00000000 0.03983329 0.00824974 0.00000000 0.95191696


75 3  0.01991665 0.00000000 0.02816639 0.00000000 0.95191696


76 2  0.01991665 0.01408320 0.00000000 0.01408320 0.95191696


77 1  0.01991665 0.01408320 0.00704160 0.00000000 0.95895856


78 4  0.00000000 0.03399984 0.00704160 0.00000000 0.95895856


79 3  0.01699992 0.00000000 0.02404152 0.00000000 0.95895856


80 2  0.01699992 0.01202076 0.00000000 0.01202076 0.95895856


81 1  0.01699992 0.01202076 0.00601038 0.00000000 0.96496894


82 4  0.00000000 0.02902068 0.00601038 0.00000000 0.96496894


83 3  0.01451034 0.00000000 0.02052072 0.00000000 0.96496894


84 2  0.01451034 0.01026036 0.00000000 0.01026036 0.96496894


85 1  0.01451034 0.01026036 0.00513018 0.00000000 0.97009912


 86 4  0.00000000 0.02477070 0.00513018 0.00000000 0.97009912


 87 3  0.01238535 0.00000000 0.01751553 0.00000000 0.97009912


 88 2  0.01238535 0.00875776 0.00000000 0.00875776 0.97009912


 89 1  0.01238535 0.00875776 0.00437888 0.00000000 0.97447800


 90 4  0.00000000 0.02114311 0.00437888 0.00000000 0.97447800


 91 3  0.01057156 0.00000000 0.01495044 0.00000000 0.97447800


 92 2  0.01057156 0.00747522 0.00000000 0.00747522 0.97447800


 93 1  0.01057156 0.00747522 0.00373761 0.00000000 0.97821561


 94 4  0.00000000 0.01804678 0.00373761 0.00000000 0.97821561


 95 3  0.00902339 0.00000000 0.01276100 0.00000000 0.97821561


 96 2  0.00902339 0.00638050 0.00000000 0.00638050 0.97821561


 97 1  0.00902339 0.00638050 0.00319025 0.00000000 0.98140586


 98 4  0.00000000 0.01540389 0.00319025 0.00000000 0.98140586


 99 3  0.00770194 0.00000000 0.01089219 0.00000000 0.98140586


100 2  0.00770194 0.00544610 0.00000000 0.00544610 0.98140586


101 1  0.00770194 0.00544610 0.00272305 0.00000000 0.98412891


102 4  0.00000000 0.01314804 0.00272305 0.00000000 0.98412891


103 3  0.00657402 0.00000000 0.00929707 0.00000000 0.98412891


104 2  0.00657402 0.00464853 0.00000000 0.00464853 0.98412891


105 1  0.00657402 0.00464853 0.00232427 0.00000000 0.98645318


106 4  0.00000000 0.01122255 0.00232427 0.00000000 0.98645318


107 3  0.00561128 0.00000000 0.00793554 0.00000000 0.98645318


108 2  0.00561128 0.00396777 0.00000000 0.00396777 0.98645318


109 1  0.00561128 0.00396777 0.00198389 0.00000000 0.98843706


110 4  0.00000000 0.00957905 0.00198389 0.00000000 0.98843706


111 3  0.00478952 0.00000000 0.00677341 0.00000000 0.98843706


112 2  0.00478952 0.00338671 0.00000000 0.00338671 0.98843706


113 1  0.00478952 0.00338671 0.00169335 0.00000000 0.99013042

----
This is fewer squeezes than starting at zone 4 initially, which takes 116 squeezes.

Posted by Charlie on 2004-02-17 08:41:23