Difference between revisions of "2004 AIME I Problems/Problem 15"
m (→Solution 2) |
m (→Solution 2) |
||
Line 28: | Line 28: | ||
We approach the problem by [[recursion]]. We [[partition]] the positive integers into the sets | We approach the problem by [[recursion]]. We [[partition]] the positive integers into the sets | ||
<cmath>\mathcal{A}_{n,k}=\{x\in\mathbb{Z}^+\,:\, d(x)=n\text{ and } x\equiv k\pmod{10}\}.</cmath> | <cmath>\mathcal{A}_{n,k}=\{x\in\mathbb{Z}^+\,:\, d(x)=n\text{ and } x\equiv k\pmod{10}\}.</cmath> | ||
− | First, we note that <math>\mathcal{A}_{1,1}=\{1\}</math>, so by the | + | First, we note that <math>\mathcal{A}_{1,1}=\{1\}</math>, so by the [[disjoint]]ness of the <math>\mathcal{A}_{n,k}</math>'s, we know that <math>1</math> is not in any of the other sets. Also, we note that <math>\mathcal{A}_{1,k}=\emptyset</math> for <math>k=0,2,3,4,5,6,7,8,9</math>. |
We claim that if <math>2\le k\le 9</math> and <math>n\ge2</math>, then <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>. To prove this, we show that <math>f</math> (the given function) maps <math>\mathcal{A}_{n,k}</math> bijectively onto <math>\mathcal{A}_{n-1,k+1}</math>. If <math>x\in \mathcal{A}_{n,k}</math>, then <math>x\equiv k\pmod{10}</math>, and <math>x\ne 1</math>, so <math>f(x)=x+1\equiv k+1\pmod{10}</math>. Also, <math>f^{(n)}(x)=1</math>, where <math>n</math> is the smallest positive integer for which this is true. Therefore, <math>f^{{n-1}}(f(x))=1</math>, where <math>n-1</math> is the smallest integer for which this is true. Thus <math>f(x)\in\mathcal{A}_{n-1,k+1}</math>. Also, since <math>f(x)=x+1</math> on this set, we see that <math>f(x)=f(y)</math> implies that <math>x=y</math>. Hence <math>f</math> is an injection. If <math>y\in\mathcal{A}_{n-1,k+1}</math>, then <math>y-1\equiv k\pmod{10}</math>, where <math>2\le k\le 9</math>, so we know that <math>f(y-1)=y</math>, and <math>y-1\in \mathcal{A}_{n,k}</math>. Therefore, <math>f</math> is a [[surjection]], so it must be a [[bijection]]. Therefore, if <math>2\le k\le 9</math> and <math>n\ge2</math>, then <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>. | We claim that if <math>2\le k\le 9</math> and <math>n\ge2</math>, then <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>. To prove this, we show that <math>f</math> (the given function) maps <math>\mathcal{A}_{n,k}</math> bijectively onto <math>\mathcal{A}_{n-1,k+1}</math>. If <math>x\in \mathcal{A}_{n,k}</math>, then <math>x\equiv k\pmod{10}</math>, and <math>x\ne 1</math>, so <math>f(x)=x+1\equiv k+1\pmod{10}</math>. Also, <math>f^{(n)}(x)=1</math>, where <math>n</math> is the smallest positive integer for which this is true. Therefore, <math>f^{{n-1}}(f(x))=1</math>, where <math>n-1</math> is the smallest integer for which this is true. Thus <math>f(x)\in\mathcal{A}_{n-1,k+1}</math>. Also, since <math>f(x)=x+1</math> on this set, we see that <math>f(x)=f(y)</math> implies that <math>x=y</math>. Hence <math>f</math> is an injection. If <math>y\in\mathcal{A}_{n-1,k+1}</math>, then <math>y-1\equiv k\pmod{10}</math>, where <math>2\le k\le 9</math>, so we know that <math>f(y-1)=y</math>, and <math>y-1\in \mathcal{A}_{n,k}</math>. Therefore, <math>f</math> is a [[surjection]], so it must be a [[bijection]]. Therefore, if <math>2\le k\le 9</math> and <math>n\ge2</math>, then <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>. |
Revision as of 00:19, 26 December 2022
Contents
[hide]Problem
For all positive integers , let
and define a sequence as follows:
and
for all positive integers
. Let
be the smallest
such that
. (For example,
and
.) Let
be the number of positive integers
such that
. Find the sum of the distinct prime factors of
.
Solution
Solution 1
We backcount the number of ways. Namely, we start at , which can only be reached if
, and then we perform
operations that either consist of
or
. We represent these operations in a string format, starting with the operation that sends
and so forth downwards. There are
ways to pick the first
operations; however, not all
of them may be
otherwise we return back to
, contradicting our assumption that
was the smallest value of
. Using complementary counting, we see that there are only
ways.
Since we performed the operation at least once in the first
operations, it follows that
, so that we no longer have to worry about reaching
again.
However, we must also account for a sequence of or more
s in a row, because that implies that at least one of those numbers was divisible by
, yet the
was never used, contradiction. We must use complementary counting again by determining the number of strings of
s of length
such that there are
s in a row. The first ten are not included since we already accounted for that scenario above, so our string of
s must be preceded by a
. There are no other restrictions on the remaining seven characters. Letting
to denote either of the functions, and
to indicate that the character appears
times in a row, our bad strings can take the forms:
There are ways to select the operations for the
s, and
places to place our
block. Thus, our answer is
, and the answer is
.
Note: This solution is quick and most similar to the official solution; however, neither this nor the official solution prove that the final results of these inverted operations are all distinct. A more sophisticated argument, such as the one below, is needed to do so.
Solution 2
We approach the problem by recursion. We partition the positive integers into the sets
First, we note that
, so by the disjointness of the
's, we know that
is not in any of the other sets. Also, we note that
for
.
We claim that if and
, then
. To prove this, we show that
(the given function) maps
bijectively onto
. If
, then
, and
, so
. Also,
, where
is the smallest positive integer for which this is true. Therefore,
, where
is the smallest integer for which this is true. Thus
. Also, since
on this set, we see that
implies that
. Hence
is an injection. If
, then
, where
, so we know that
, and
. Therefore,
is a surjection, so it must be a bijection. Therefore, if
and
, then
.
We also claim that if ,
and
, then
. The proof is the same as in the previous paragraph, though some additional clarification is needed to prove that
is a surjection. If
, or rather
, then if
, we see that
, and then
, not
as in the prior argument. However, this does not happen if
. It is easy to check that
. Therefore, the only time that the above argument could fail is if
and
. But in every other case,
.
Next, we claim that if , then
If
, then
, which is clearly an injective map. Also,
, where
is the smallest positive integer for which this is true. Therefore,
, where
is the smallest integer for which this is true. Thus
for some
. Conversely, if
, then
, so
, so
.
Based on these bijections, if we let , then
Let
. Then by adding the above equations (valid if
), we find that
Now by using the above relations repeatedly, we find
The first relation will only be valid if
. Therefore,
for
. For smaller values, it is easy to use the relations to compute that the terms are powers of
, although we note that
because of the failure of the above argument.
After this, we can simply use the recurrence relation for
, finding
Therefore, there are
positive integers
with
. This factors as
, where
is prime. Thus the answer is
.
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.