Question

A long thin strip of paper is $1024$ units in length, $1$ unit in width, and is divided into $1024$ unit squares. The paper is folded in half repeatedly. For the first fold, the right end of the paper is folded over to coincide with and lie on top of the left end. The result is a $512$ by $1$ strip of double thickness. Next, the right end of this strip is folded over to coincide with and lie on top of the left end, resulting in a $256$ by $1$ strip of quadruple thickness. This process is repeated $8$ more times. After the last fold, the strip has become a stack of $1024$ unit squares. How many of these squares lie below the square that was originally the $942$ nd square counting from the left?

Answer

Solution:

After $f$ folds the strip is $2^{10-f}$ squares long and $2^f$ layers thick, so the positions $L$ from the left and $R$ from the right satisfy $L + R = 2^{10-f} + 1,$ and the positions $B$ from the bottom and $T$ from the top satisfy $B + T = 2^f + 1.$ When the right half is folded over onto the left, a square in the left half keeps its $L$ and $B,$ while a square in the right half is flipped: its new $L$ is its old $R,$ and its new $T$ is its old $B.$

The $942$ nd square starts at $(L, B) = (942, 1).$ Applying the rule through the ten folds gives $(83, 2),\ (83, 2),\ (83, 2),\ (46, 15),\ (19, 18),\ (14, 47),\ (3, 82),\ (3, 82),\ (2, 431),\ (1, 594).$ For example, at the fourth fold the strip has length $128$ and $L = 83 \gt 64,$ so the new $L$ is $128 + 1 - 83 = 46$ and the new $T$ is the old $B = 2,$ making $B = 16 + 1 - 2 = 15.$

In the final stack of $1024$ squares, this square sits at height $594$ from the bottom, so $594 - 1 = 593$ squares lie below it.

2004 AIME II Problem 15

Solution:

Problem 15 in Other Years