Difference between revisions of "2004 AIME I Problems/Problem 15"
Mathgeek2006 (talk | contribs) m (→Solution) |
|||
Line 12: | Line 12: | ||
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 complementary 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: | 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 complementary 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: | ||
− | < | + | <cmath>\begin{align*} |
&\underbrace{BA^{[10]}}\square \square \square \square \square \square \square \square \\ | &\underbrace{BA^{[10]}}\square \square \square \square \square \square \square \square \\ | ||
&\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \square \\ | &\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \square \\ | ||
Line 18: | Line 18: | ||
&\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \square \\ | &\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \square \\ | ||
&\square \square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\ | &\square \square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\ | ||
− | \end{align*}</ | + | \end{align*}</cmath> |
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>. | 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>. |
Revision as of 16:50, 13 March 2015
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
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. Thus the remaining
operations can be picked in
ways, with a total of
strings.
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, then 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
.
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.