Difference between revisions of "2022 AIME I Problems/Problem 6"
(→Solution 3) |
|||
(19 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
− | == | + | == Problem == |
+ | Find the number of ordered pairs of integers <math>(a, b)</math> such that the sequence<cmath>3, 4, 5, a, b, 30, 40, 50</cmath>is strictly increasing and no set of four (not necessarily consecutive) terms forms an arithmetic progression. | ||
− | divide cases into <math>7\leq a<20; 21\leq a\leq28</math>. | + | == Solution 1== |
− | There are three cases that arithmetic sequence forms: <math>3,12,21,30;4,16,28,40;3,5,7,9</math>. So | + | Since <math>3,4,5,a</math> and <math>3,4,5,b</math> cannot be an arithmetic progression, <math>a</math> or <math>b</math> can never be <math>6</math>. Since <math>b, 30, 40, 50</math> and <math>a, 30, 40, 50</math> cannot be an arithmetic progression, <math>a</math> and <math>b</math> can never be <math>20</math>. Since <math>a < b</math>, there are <math>{24 - 2 \choose 2} = 231</math> ways to choose <math>a</math> and <math>b</math> with these two restrictions in mind. |
+ | |||
+ | However, there are still specific invalid cases counted in these <math>231</math> pairs <math>(a,b)</math>. Since | ||
+ | <cmath>3,5,a,b</cmath> | ||
+ | cannot form an arithmetic progression, <math>\underline{(a,b) \neq (7,9)}</math>. | ||
+ | <cmath>a,b,30,50</cmath> | ||
+ | cannot be an arithmetic progression, so <math>(a,b) \neq (-10,10)</math>; however, since this pair was not counted in our <math>231</math>, we do not need to subtract it off. | ||
+ | <cmath>3,a,b,30</cmath> | ||
+ | cannot form an arithmetic progression, so <math>\underline{(a,b) \neq (12,21)}</math>. | ||
+ | <cmath>4, a, b, 40</cmath> | ||
+ | cannot form an arithmetic progression, so <math>\underline{(a,b) \neq (16,28)}</math>. | ||
+ | <cmath>5, a,b, 50</cmath> | ||
+ | cannot form an arithmetic progression, <math>(a,b) \neq 20, 35</math>; however, since this pair was not counted in our <math>231</math> (since we disallowed <math>a</math> or <math>b</math> to be <math>20</math>), we do not to subtract it off. | ||
+ | |||
+ | Also, the sequences <math>(3,a,b,40)</math>, <math>(3,a,b,50)</math>, <math>(4,a,b,30)</math>, <math>(4,a,b,50)</math>, <math>(5,a,b,30)</math> and <math>(5,a,b,40)</math> will never be arithmetic, since that would require <math>a</math> and <math>b</math> to be non-integers. | ||
+ | |||
+ | So, we need to subtract off <math>3</math> progressions from the <math>231</math> we counted, to get our final answer of <math>\boxed{228}</math>. | ||
+ | |||
+ | ~ 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 <math>\textbf{1}</math> 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 <math>a, b</math>, 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,), <math>a, b</math>, (one of 30, 40, 50). If this is to be the case, then let <math>a</math> be the starting value in the sequence. The sequence will be <math>a, a+d, a+2d, a+3d</math>; We see that if we subtract the largest term by the smallest term we have <math>3d</math>, 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 <math>3,a,b,30; 4,a,b,40; 5,a,b,50</math>. Of these, only the last is invalid because it gives <math>b = 35</math>, larger than our bounds <math>6<a<b<30</math>. Therefore, we subtract <math>\textbf{2}</math> from this case. | ||
+ | |||
+ | Our final answer is <math>231 - 1 - 2 = \boxed{228}</math> | ||
+ | |||
+ | ~KingRavi | ||
+ | |||
+ | ==Solution 3== | ||
+ | Denote <math>S = \left\{ (a, b) : 6 \leq a < b \leq 29 \right\}</math>. | ||
+ | |||
+ | Denote by <math>A</math> a subset of <math>S</math>, such that there exists an arithmetic sequence that has 4 terms and includes <math>a</math> but not <math>b</math>. | ||
+ | |||
+ | Denote by <math>B</math> a subset of <math>S</math>, such that there exists an arithmetic sequence that has 4 terms and includes <math>b</math> but not <math>a</math>. | ||
+ | |||
+ | Hence, <math>C</math> is a subset of <math>S</math>, such that there exists an arithmetic sequence that has 4 terms and includes both <math>a</math> and <math>b</math>. | ||
+ | |||
+ | Hence, this problem asks us to compute | ||
+ | <cmath> | ||
+ | \[ | ||
+ | | S | - \left( | A | + | B | + | C | \right) . | ||
+ | \] | ||
+ | </cmath> | ||
+ | |||
+ | First, we compute <math>| S |</math>. | ||
+ | |||
+ | We have <math>| S | = \binom{29 - 6 + 1}{2} = \binom{24}{2} = 276</math>. | ||
+ | |||
+ | Second, we compute <math>| A |</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math>: <math>a = 6</math>. | ||
+ | |||
+ | We have <math>b = 8 , \cdots , 19, 21, 22, \cdots, 29</math>. | ||
+ | Thus, the number of solutions is 22. | ||
+ | |||
+ | <math>\textbf{Case 2}</math>: <math>a = 20</math>. | ||
+ | |||
+ | We have <math>b = 21, 22, \cdots , 29</math>. | ||
+ | Thus, the number of solutions is 9. | ||
+ | |||
+ | Thus, <math>| A | = 22 + 9 = 31</math>. | ||
+ | |||
+ | Third, we compute <math>| B |</math>. | ||
+ | |||
+ | In <math>B</math>, we have <math>b = 6, 20</math>. However, because <math>6 \leq a < b</math>, we have <math>b \geq 7</math>. | ||
+ | Thus, <math>b = 20</math>. | ||
+ | |||
+ | This implies <math>a = 7, 8, 9, 11, 12, \cdots , 19</math>. Note that <math>(a, b)=(10, 20)</math> belongs in <math>C</math>. | ||
+ | |||
+ | Thus, <math>| B | = 12</math>. | ||
+ | |||
+ | Fourth, we compute <math>| C |</math>. | ||
+ | |||
+ | <math>\textbf{Case 1}</math>: In the arithmetic sequence, the two numbers beyond <math>a</math> and <math>b</math> are on the same side of <math>a</math> and <math>b</math>. | ||
+ | |||
+ | Hence, <math>(a, b) = (6 , 7), (7, 9) , (10, 20)</math>. | ||
+ | Therefore, the number solutions in this case is 3. | ||
+ | |||
+ | <math>\textbf{Case 2}</math>: In the arithmetic sequence, the two numbers beyond <math>a</math> and <math>b</math> are on the opposite sides of <math>a</math> and <math>b</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.1}</math>: The arithmetic sequence is <math>3, a, b, 30</math>. | ||
+ | |||
+ | Hence, <math>(a, b) = (12, 21)</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.2}</math>: The arithmetic sequence is <math>4, a, b, 40</math>. | ||
+ | |||
+ | Hence, <math>(a, b) = (16, 28)</math>. | ||
+ | |||
+ | <math>\textbf{Case 2.3}</math>: The arithmetic sequence is <math>5, a, b, 50</math>. | ||
+ | |||
+ | Hence, <math>(a, b) = (20, 35)</math>. However, the sequence <math>... 20, 35, 30, 40, 50</math> is not strictly increasing. | ||
+ | |||
+ | Putting two cases together, <math>| C | = 65.</math> | ||
+ | |||
+ | Therefore, | ||
+ | <cmath> | ||
+ | | S | - \left( | A | + | B | + | C | \right) = 276 - \left( 31 + 12 + 5 \right) = \boxed{228}. | ||
+ | </cmath> | ||
+ | |||
+ | ~Steven Chen (www.professorchenedu.com) | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | divide cases into <math>7\leq a<20; 21\leq a\leq28</math>.(Notice that <math>a</math> can't be equal to <math>6,20</math>, that's why I divide them into two parts. | ||
+ | There are three cases that arithmetic sequence forms: <math>3,12,21,30;4,16,28,40;3,5,7,9</math>.(NOTICE that <math>5,20,35,50</math> IS NOT A VALID SEQUENCE!) | ||
+ | So when <math>7\leq a<20</math>, there are <math>10+11+12+...+22-3-13=192</math> possible ways( 3 means the arithmetic sequence and 13 means there are 13 "a" s and b cannot be 20) | ||
+ | |||
+ | When <math>21\leq a \leq 28</math>, there are <math>1+2+\cdots+8=36</math> ways. | ||
+ | |||
+ | In all, there are <math>192+36=\boxed{228}</math> possible sequences. | ||
~bluesoul | ~bluesoul | ||
+ | |||
+ | ==See Also== | ||
+ | {{AIME box|year=2022|n=I|num-b=5|num-a=7}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 22:55, 26 March 2023
Problem
Find the number of ordered pairs of integers such that the sequence
is 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 22.
:
.
We have .
Thus, the number of solutions is 9.
Thus, .
Third, we compute .
In , we have
. However, because
, we have
.
Thus,
.
This implies . Note that
belongs in
.
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, . However, the sequence
is not strictly increasing.
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.