Difference between revisions of "2017 AIME I Problems/Problem 9"
Jackshi2006 (talk | contribs) (→Solution 6 (bash, slower, but safer)) |
Jackshi2006 (talk | contribs) (→Solution 5) |
||
Line 54: | Line 54: | ||
<math>b_n = (20+n)(n+1)</math>. | <math>b_n = (20+n)(n+1)</math>. | ||
− | Notice that both can't have a factor of 3. Thus we can limit our search range of n to <math>n \equiv 7,8 \pmod{9}</math>. Testing values for n in our search range (like 7,8,16,17,25,26...), we get that 35 is the least n. But, don't write that down! Remember, <math>b_n = 2a_{n+10}</math>, so, the 35th term in b corresponds to the 45th term in a. Thus our answer is <math>\boxed{045}</math> | + | Notice that both can't have a factor of 3. Thus we can limit our search range of n to <math>n \equiv 7,8 \pmod{9}</math>. Testing values for n in our search range (like 7,8,16,17,25,26...), we get that 35 is the least n. But, don't write that down! Remember, <math>b_n = 2a_{n+10}</math>, so, the 35th term in b corresponds to the 45th term in a. Thus our answer is <math>\boxed{045}</math>. |
-AlexLikeMath | -AlexLikeMath |
Revision as of 17:50, 18 May 2020
Contents
Problem 9
Let , and for each integer
let
. Find the least
such that
is a multiple of
.
Solution 1
Writing out the recursive statement for and summing them gives
Which simplifies to
Therefore,
is divisible by 99 if and only if
is divisible by 99, so
needs to be divisible by 9 and 11. Assume that
is a multiple of 11. Writing out a few terms,
, we see that
is the smallest
that works in this case. Next, assume that
is a multiple of 11. Writing out a few terms,
, we see that
is the smallest
that works in this case. The smallest
is
.
Note that we can also construct the solution using CRT by assuming either divides
and
divides
, or
divides
and
divides
, and taking the smaller solution.
Solution 2
By looking at the first few terms, we can see that
This implies
Since
, we can rewrite the equivalence, and simplify
The only squares that are congruent to
are
and
, so
yields
as the smallest integer solution.
yields
as the smallest integer solution.
yields
as the smallest integer solution.
yields
as the smallest integer solution. However,
must be greater than
.
The smallest positive integer solution greater than is
.
Solution 3
. Using the steps of the previous solution we get up to
. This gives away the fact that
so either
or
must be a multiple of 9.
Case 1 (): Say
and after simplification
.
Case 2: (): Say
and after simplification
.
As a result must be a divisor of
and after doing some testing in both cases the smallest value that works is
.
~First
Solution 4 (not good, risky)
We just notice that , so we are just trying to find
modulo
, or
modulo
. Also, the sum to
is divisible by
, and is the first one that is. Thus, if we sum to
the
is cut off and thus is just a sum to
.
Without checking whether there are other sums congruent to , we can just write the answer to be
.
Solution 5
Let . We can find a formula for
:
.
Notice that both can't have a factor of 3. Thus we can limit our search range of n to . Testing values for n in our search range (like 7,8,16,17,25,26...), we get that 35 is the least n. But, don't write that down! Remember,
, so, the 35th term in b corresponds to the 45th term in a. Thus our answer is
.
-AlexLikeMath
Solution 6 (bash, slower, but safer)
The first thing you should realize is that each term after the tenth is another two-digit number chained to the last number. 10, 1011, 101112, etc. Now the fact that the sequence starts at 10 can be completely discarded for this solution. Just consider a(10) then same as a(1), and we can add nine to the answer at the end.
The second step is to split 99 as 9 and 11 and solve for divisibility rules individually. Let's start with 11 because it gives us the most information to continue.
In any number generated, if the numbers don't go beyond 20, then the highest number we can get is 10111213141516171819, with every odd digit being 1. This is a little risky because we are assuming that it doesn't exceed 20. If someone wanted to be absolutely sure they could continue, but this is unnecessary later and a big hassle. Anyways, now we write an equation to check for divisibility by 11. The expression being ((((n-1) + 0) * n)/2)-n. (apologies for latex illiteracy, please add latex if you can) I don't think I need to go in-depth, but the concept here is to add 0 to (nth-1 term) altogether, then subtract the number of ones in it, which is n. Simplify to (n(n-3))/2 congruent to 0 mod 11. Now notice the divide by two can be discarded because one of n or (n-3) will be even. So if n or n-3 is to be divisible by 11, we can make a simple list.
n = 0, 3, 11, 14, 22, 25, 33, 36, 44, 47, etc.
Now we test each n for divisibility by 9.
This is done by making a list that ultimately calculates the sum of every digit in the large number.
n(1) to n(10) has the first digit 1. n(11) to n(20) has the first digit 2, and so on.
The necessary thing to realize is that the sum of all digits 0-9 is divisible by 9, so we only have to solve for the sum of the first digits, and then the short list of second digits.
For example, let's test n=25.
So we know that 25 include both 1-10 and 11-20, so that's 10 + 20 right away. 21-25 contains 5 numbers that have the first digit 3, so +15. Then we add 0-4 together, which is 10. 10+20+15+10=55, which is not divisible by 9, so it is not the answer.
Do this for just a minute you get that 36 sums to 99, a multiple of nine! So n(36) is the answer, right? Don't forget we have to add 9 because we translated n(10) to n(1) at the very beginning!
Finally, after a short bash, we get .
-jackshi2006
See also
2017 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
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.