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 I Problems/Problem 15"

m (LaTeX style)
(solution)
Line 4: Line 4:
 
f(x)=\begin{cases}1 & \text{if x = 1}}\\ \frac x{10} & \text{if x is divisible by 10}\\ x+1 & \text{otherwise}\end{cases}
 
f(x)=\begin{cases}1 & \text{if x = 1}}\\ \frac x{10} & \text{if x is divisible by 10}\\ x+1 & \text{otherwise}\end{cases}
 
</cmath>
 
</cmath>
−
and define a sequence as follows: <math>x_1=x</math> and <math>x_{n+1}=f(x_n)</math> for all positive integers <math>n</math>. Let <math>d(x)</math> be the smallest <math>n</math> such that <math>x_n=1</math>. (For example, <math>d(100)=3</math> and <math>d(87)=7</math>.) Let <math>m</math> be the number of positive integers <math>x</math> such that <math>d(x)=20</math>. Find the sum of the distinct prime factors of <math>m</math>.
+
and define a [[sequence]] as follows: <math>x_1=x</math> and <math>x_{n+1}=f(x_n)</math> for all positive integers <math>n</math>. Let <math>d(x)</math> be the smallest <math>n</math> such that <math>x_n=1</math>. (For example, <math>d(100)=3</math> and <math>d(87)=7</math>.) Let <math>m</math> be the number of positive integers <math>x</math> such that <math>d(x)=20</math>. Find the sum of the distinct prime factors of <math>m</math>.
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
We backcount the number of ways. Namely, we start at <math>x_{20} = 1</math>, which can only be reached if <math>x_{19} = 10</math>, and then we perform <math>18</math> operations that either consist of <math>A: (-1)</math> or <math>B: (\times 10)</math>. We represent these operations in a string format, starting with the operation that sends <math>f(x_{18}) = x_{19}</math> and so forth downwards. There are <math>2^9</math> ways to pick the first <math>9</math> operations; however, not all <math>9</math> of them may be <math>A: (-1)</math> otherwise we return back to <math>x_{10} = 1</math>, contradicting our assumption that <math>20</math> was the smallest value of <math>n</math>. By the [[complement principle]], we only have <math>2^9 - 1</math> ways.
 +
 
 +
Since we performed the operation <math>B: (\times 10)</math> at least once in the first <math>9</math> operations, it follows that <math>x_{10} \ge 20</math>, so that we no longer have to worry about reaching <math>1</math> again. Thus the remaining <math>9</math> operations can be picked in <math>2^9</math> ways, with a total of <math>2^9(2^9 - 1) = 2^{18} - 2^9</math> strings.
 +
 
 +
However, we must also account for a sequence of <math>10</math> or more <math>A: (-1)</math>s in a row, because that implies that at least one of those numbers was divisible by <math>10</math>, yet the <math>\frac{x}{10}</math> was never used, contradiction. We must use complement counting again by determining the number of strings of <math>A,B</math>s of length <math>18</math> such that there are <math>10</math> <math>A</math>s in a row. The first ten are not included since we already accounted for that scenario above, so our string of <math>10</math> <math>A</math>s must be preceded by a <math>B</math>. There are no other restrictions on the remaining seven characters. Letting <math>\square</math> to denote either of the functions, and <math>^{[k]}</math> to indicate that the character appears <math>k</math> times in a row, then our bad strings can take the forms:
 +
<center><math>\begin{align*}
 +
&\underbrace{BA^{[10]}}\square \square \square \square \square \square \square \square \\
 +
&\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \square \\
 +
&\qquad \quad \cdots \quad \cdots \\
 +
&\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \square \\
 +
&\square \square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\
 +
\end{align*}</math></center>
 +
 
 +
There are <math>2^7</math> ways to select the operations for the <math>7</math> <math>\square</math>s, and <math>8</math> places to place our <math>BA^{[10]}</math> block. Thus, our answer is <math>2^{18} - 2^9 - 8 \cdot 2^7 = 2^9 \times 509</math>, and the answer is <math>\boxed{511}</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2004|n=I|num-b=14|after=Last Question}}
 
{{AIME box|year=2004|n=I|num-b=14|after=Last Question}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]
 +
[[Category:Intermediate Number Theory Problems]]

Revision as of 13:55, 8 June 2008

Problem

For all positive integers $x$, let 

\[f(x)=\begin{cases}1 & \text{if x = 1}}\\ \frac x{10} & \text{if x is divisible by 10}\\ x+1 & \text{otherwise}\end{cases}\] (Error compiling LaTeX. Unknown error_msg)

and define a sequence as follows: $x_1=x$ and $x_{n+1}=f(x_n)$ for all positive integers $n$. Let $d(x)$ be the smallest $n$ such that $x_n=1$. (For example, $d(100)=3$ and $d(87)=7$.) Let $m$ be the number of positive integers $x$ such that $d(x)=20$. Find the sum of the distinct prime factors of $m$.

Solution

We backcount the number of ways. Namely, we start at $x_{20} = 1$, which can only be reached if $x_{19} = 10$, and then we perform $18$ operations that either consist of $A: (-1)$ or $B: (\times 10)$. We represent these operations in a string format, starting with the operation that sends $f(x_{18}) = x_{19}$ and so forth downwards. There are $2^9$ ways to pick the first $9$ operations; however, not all $9$ of them may be $A: (-1)$ otherwise we return back to $x_{10} = 1$, contradicting our assumption that $20$ was the smallest value of $n$. By the complement principle, we only have $2^9 - 1$ ways.

Since we performed the operation $B: (\times 10)$ at least once in the first $9$ operations, it follows that $x_{10} \ge 20$, so that we no longer have to worry about reaching $1$ again. Thus the remaining $9$ operations can be picked in $2^9$ ways, with a total of $2^9(2^9 - 1) = 2^{18} - 2^9$ strings.

However, we must also account for a sequence of $10$ or more $A: (-1)$s in a row, because that implies that at least one of those numbers was divisible by $10$, yet the $\frac{x}{10}$ was never used, contradiction. We must use complement counting again by determining the number of strings of $A,B$s of length $18$ such that there are $10$ $A$s in a row. The first ten are not included since we already accounted for that scenario above, so our string of $10$ $A$s must be preceded by a $B$. There are no other restrictions on the remaining seven characters. Letting $\square$ to denote either of the functions, and $^{[k]}$ to indicate that the character appears $k$ times in a row, then our bad strings can take the forms:

$\begin{align*}

&\underbrace{BA^{[10]}}\square \square \square \square \square \square \square \square \\ &\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \square \\ &\qquad \quad \cdots \quad \cdots \\ &\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \square \\ &\square \square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\

\end{align*}$ (Error compiling LaTeX. Unknown error_msg)

There are $2^7$ ways to select the operations for the $7$ $\square$s, and $8$ places to place our $BA^{[10]}$ block. Thus, our answer is $2^{18} - 2^9 - 8 \cdot 2^7 = 2^9 \times 509$, and the answer is $\boxed{511}$.

See also

2004 AIME I (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_I_Problems/Problem_15&oldid=26352"