Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2004 AIME II Problems/Problem 15"

m
(solution by t0rajir0u)
Line 1: Line 1:
 
== Problem ==
 
== 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 942nd square counting from the left?
+
A long thin strip of paper is <math>1024</math> units in length, <math>1</math> unit in width, and is divided into <math>1024</math> 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 <math>512</math> by <math>1</math> 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 <math>256</math> by <math>1</math> strip of quadruple thickness. This process is repeated <math>8</math> more times. After the last fold, the strip has become a stack of <math>1024</math> unit squares. How many of these squares lie below the square that was originally the <math>942</math>nd square counting from the left?
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
Number the squares <math>0, 1, 2, 3, ... 2^{k} - 1</math>.  In this case <math>k = 10</math>, but we will consider more generally to find an inductive solution.  Call <math>s_{n, k}</math> the number of squares below the <math>n</math> square after the final fold in a strip of length <math>2^{k}</math>.
 +
 
 +
Now, consider the strip of length <math>1024</math>.  The problem asks for <math>s_{941, 10}</math>.  We can derive some useful recurrences for <math>s_{n, k}</math> as follows:  Consider the first fold.  Each square <math>s</math> is now paired with the square <math>2^{k} - s - 1</math>.  Now, imagine that we relabel these pairs with the indices <math>0, 1, 2, 3... 2^{k - 1} - 1</math> - then the <math>s_{n, k}</math> value of the pairs correspond with the <math>s_{n, k - 1}</math> values - specifically, double, and maybe <math>+ 1</math> (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 <math>1024</math>, the <math>941</math> square is on top of the <math>82</math> square.  We can then write
 +
 
 +
<cmath>s_{941, 10} = 2s_{82, 9} + 1</cmath>
 +
 
 +
(We add one because <math>941</math> 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):
 +
 
 +
<cmath>s_{82, 9} = 2s_{82, 8} = 4s_{82, 7} = 8s_{127 - 82, 6} = 8s_{45, 6}</cmath>
 +
 
 +
<cmath>s_{45, 6} = 2s_{63 - 45, 5} + 1 = 2s_{18, 5} + 1 = 4s_{31 - 18, 4} + 1 = 4s_{13, 4} + 1</cmath>
 +
 
 +
<cmath>s_{13, 4} = 2s_{15 - 13, 3} + 1 = 2s_{2, 3}</cmath>
 +
 
 +
We can easily calculate <math>s_{2, 3} = 4</math> from a diagram.  Plugging back in,
 +
 
 +
<cmath>\begin{align*} s_{13, 4} &= 9 \\
 +
s_{45, 6} &= 37 \\
 +
s_{82, 9} &= 296 \\
 +
s_{941, 10} &= \boxed{593}</cmath>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2004|n=II|num-b=14|after=Last Question}}
 
{{AIME box|year=2004|n=II|num-b=14|after=Last Question}}
 +
 +
[[Category:Intermediate Algebra Problems]]

Revision as of 21:32, 28 July 2008

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

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}\]

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} (Error compiling LaTeX. Unknown error_msg)

See also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_15&oldid=27240"