Maths Olympiad Prep

Library / /691 of 740

Algebra Difficulty 5.7 AIME, harder Prove it United States

Problem:

The very hungry caterpillar lives on the number line. For each non-zero integer ii, a fruit sits on the point with coordinate ii. The caterpillar moves back and forth; whenever he reaches a point with food, he eats the food, increasing his weight by one pound, and turns around. The caterpillar moves at a speed of 2w2^{-w} units per day, where ww is his weight. If the caterpillar starts off at the origin, weighing zero pounds, and initially moves in the positive xx direction, after how many days will he weigh 10 pounds?

Solution

Solution:

On the nnth straight path, the caterpillar travels nn units before hitting food and his weight is n1n-1. Then his speed is 21n2^{1-n}. Then right before he turns around for the nnth time, he has traveled a total time of i=1ni21i=12i=1ni2i\sum_{i=1}^{n} \frac{i}{2^{1-i}}=\frac{1}{2} \sum_{i=1}^{n} i \cdot 2^{i}. We want to know how many days the caterpillar moves before his weight is 10, so we want to take n=10n=10 so that his last straight path was taken at weight 9. Hence we want to evaluate S=12i=110i2iS=\frac{1}{2} \sum_{i=1}^{10} i \cdot 2^{i}. Note that 2S=12i=211(i1)2i2S=\frac{1}{2} \sum_{i=2}^{11}(i-1) \cdot 2^{i}, so S=2SS=12(11211i=1102i)=12(10211211+2)=9217S=2S-S=\frac{1}{2}\left(11 \cdot 2^{11}-\sum_{i=1}^{10} 2^{i}\right)=\frac{1}{2}\left(10 \cdot 2^{11}-2^{11}+2\right)=9217.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.