2022 AIME I Problems/Problem 6
Problem
Find the number of ordered pairs of integers such that the sequenceis strictly increasing and no set of four (not necessarily consecutive) terms forms an arithmetic progression.
Solution 1
Since and cannot be an arithmetic progression, or can never be . Since and cannot be an arithmetic progression, and can never be . Since , there are ways to choose and with these two restrictions in mind.
However, there are still specific invalid cases counted in these pairs . Since cannot form an arithmetic progression, . cannot be an arithmetic progression, so ; however, since this pair was not counted in our , we do not need to subtract it off. cannot form an arithmetic progression, so . cannot form an arithmetic progression, so . cannot form an arithmetic progression, ; however, since this pair was not counted in our (since we disallowed or to be ), we do not to subtract it off.
Also, the sequences , , , , and will never be arithmetic, since that would require and to be non-integers.
So, we need to subtract off progressions from the we counted, to get our final answer of .
~ ihatemath123
Solution 2 (Rigorous)
We will follow the solution from earlier in a rigorous manner to show that there are no other cases missing.
We recognize that an illegal sequence (defined as one that we subtract from our 231) can never have the numbers {3, 4} and {4,5} because we have not included a 6 in our count. Similarly, sequences with {30,40} and {40,50} will not give us any subtractions because those sequences must all include a 20. Let's stick with the lower ones for a minute: if we take them two at a time, then {3,5} will give us the subtraction of 1 sequence {3,5,7,9}. We have exhausted all pairs of numbers we can take, and if we take the triplet of single digit numbers, the only possible sequence must have a 6, which we already don't count. Therefore, we subtract from the count of illegal sequences with any of the single-digit numbers and none of the numbers 30,40,50. (Note if we take only 1 at a time, there will have to be 3 of , which is impossible.)
If we have the sequence including {30,50}, we end up having negative values, so these do not give us any subtractions, and the triplet {30,40,50} gives us a 20. Hence by the same reasoning as earlier, we have 0 subtractions from the sequences with these numbers and none of the single digit numbers {3,4,5}.
Finally, we count the sequences that are something like (one of 3,4,5,), , (one of 30, 40, 50). If this is to be the case, then let be the starting value in the sequence. The sequence will be ; We see that if we subtract the largest term by the smallest term we have , so the subtraction of one of (30,40,50) and one of (3,4,5) must be divisible by 3. Therefore the only sequences possible are . Of these, only the last is invalid because it gives , larger than our bounds . Therefore, we subtract from this case.
Our final answer is
~KingRavi
Solution 3
Denote .
Denote by a subset of , such that there exists an arithmetic sequence that has 4 terms and includes but not .
Denote by a subset of , such that there exists an arithmetic sequence that has 4 terms and includes but not .
Hence, is a subset of , such that there exists an arithmetic sequence that has 4 terms and includes both and .
Hence, this problem asks us to compute
First, we compute .
We have .
Second, we compute .
: .
We have . Thus, the number of solutions is 21.
: .
We have . Thus, the number of solutions is 9.
Thus, .
Third, we compute .
In , we have . However, because , we have . Thus, .
This implies . Thus, .
Fourth, we compute .
: In the arithmetic sequence, the two numbers beyond and are on the same side of and .
Hence, . Therefore, the number solutions in this case is 3.
: In the arithmetic sequence, the two numbers beyond and are on the opposite sides of and .
: The arithmetic sequence is .
Hence, .
: The arithmetic sequence is .
Hence, .
: The arithmetic sequence is .
Hence, .
Putting two cases together, .
Therefore,
~Steven Chen (www.professorchenedu.com)
Solution 4
divide cases into .(Notice that can't be equal to , that's why I divide them into two parts. There are three cases that arithmetic sequence forms: .(NOTICE that IS NOT A VALID SEQUENCE!) So when , there are possible ways( 3 means the arithmetic sequence and 13 means there are 13 "a" s and b cannot be 20)
When , there are ways.
In all, there are possible sequences.
~bluesoul
See Also
2022 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 5 |
Followed by Problem 7 | |
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.