2004 AIME II Problems/Problem 15

Problem

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?

Solution 1

Number the squares $0, 1, 2, 3, ... 2^{k} - 1$ . In this case $k = 10$ , but we will consider more generally to find an inductive solution. Call $s_{n, k}$ the number of squares below the $n$ square after the final fold in a strip of length $2^{k}$ .

Now, consider the strip of length $1024$ . The problem asks for $s_{941, 10}$ . We can derive some useful recurrences for $s_{n, k}$ as follows: Consider the first fold. Each square $s$ is now paired with the square $2^{k} - s - 1$ . Now, imagine that we relabel these pairs with the indices $0, 1, 2, 3... 2^{k - 1} - 1$ - then the $s_{n, k}$ value of the pairs correspond with the $s_{n, k - 1}$ values - specifically, double, and maybe $+ 1$ (if the member of the pair that you're looking for is the top one at the final step).

So, after the first fold on the strip of length $1024$ , the $941$ square is on top of the $82$ square. We can then write

$s_{941, 10} = 2s_{82, 9} + 1$

(We add one because $941$ is the odd member of the pair, and it will be on top. This is more easily visually demonstrated than proven.) We can repeat this recurrence, adding one every time we pair an odd to an even (but ignoring the pairing if our current square is the smaller of the two):

$s_{82, 9} = 2s_{82, 8} = 4s_{82, 7} = 8s_{127 - 82, 6} = 8s_{45, 6}$

$s_{45, 6} = 2s_{63 - 45, 5} + 1 = 2s_{18, 5} + 1 = 4s_{31 - 18, 4} + 1 = 4s_{13, 4} + 1$

$s_{13, 4} = 2s_{15 - 13, 3} + 1 = 2s_{2, 3}+1$

We can easily calculate $s_{2, 3} = 4$ from a diagram. Plugging back in,

$\begin{align*} s_{13, 4} &= 9 \\ s_{45, 6} &= 37 \\ s_{82, 9} &= 296 \\ s_{941, 10} &= \boxed{593}\end{align*}$

Solution 2

More brute force / thinking about the question logically. We can find the number of squares above the number instead. If the number doesn't change position, then we add the number of squares we just folded. Otherwise, we just take the number of squares under it before we folded and now these are above the number.

First its in position $942$ with $0$ spaces over it. We flip once, since $942$ is to the right it gets flipped onto itself, going from position $942$ to $1025 - 942 = 83$ . Now its in position 83, still has $0$ spaces over it.

Flip again, it's still in position 83 but now, since it didn't move position, we add the thickness of the fold we just flipped, which is 2. So now there are $2$ spaces over it.

Flip again, its to the left of the fold again, so we add $4$ squares to get $6$ .

Flip again, it goes from $83 \to 46$ in position, and there was $8 - 6 - 1 = 1$ square below our number before we flipped, so now that one number is above it.

Flip again, it goes $46 \to 19$ , and now there were $16 - 1 - 1 = 14$ squares below it so now they are above it.

Flip again, it goes $19 \to 14$ , and there were $32 - 14 - 1 = 17$ squares below it and now they are above it.

Flip again, it goes $14 \to 3$ and there were $64 - 17 - 1 = 46$ squares below it and now they are above it.

Flip again, it stays in position, so we add $128$ to get $174$ .

Flip again, it goes $3 \to 2$ , and there were $256 - 174 - 1 = 81$ squares below it and now they are above it.

Flip again, it goes $2 \to 1$ , and there were $512 - 81 - 1 = 430$ squares below it and now they are above it.

Since the question asks for how many squares were below our number, our answer is $1024 - 430 - 1 = 593$ .

Solution 3

We can keep track of the position of the square labeled 942 in each step. We use an $(x,y)$ coordinate system, so originally the 942 square is in the position $(942,1)$ . In general, suppose that we've folded the strip into an array $r=2^k$ squares wide and $c=1024/r=2^{10-k}$ squares tall (so we've made $10-k$ folds). Then if a square occupies the location $(x,y)$ , we find that after the next fold, it will be in the location described by the procedure $(x,y)\to\begin{cases}(x,y)&\text{if }x\le 2^{k-1}\\ (r+1-x,2c+1-y)&\text{otherwise}.\end{cases}$ Therefore, we can keep track of the square's location in the following table. $\begin{array}{c|c|c} (x,y)&\text{rows}&\text{columns}\\\hline (942,1)&1024&1\\ (83,2)&512&2\\ (83,2)&256&4\\ (83,2)&128&8\\ (46,15)&64&16\\ (19,18)&32&32\\ (14,47)&16&64\\ (3,82)&8&128\\ (3,82)&4&256\\ (2,431)&2&512\\ (1,594)&1&1024.\\ \end{array}$ Therefore, at the end of the process, the square labeled 942 will be in the position $(1,594)$ , i.e., it will be above $\boxed{593}$ squares.

2004 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2004 AIME II Problems/Problem 15

Contents

Problem

Solution 1

Solution 2

Solution 3

See also