Difference between revisions of "2019 AIME II Problems/Problem 14"
(revised solution) |
|||
(4 intermediate revisions by one other user not shown) | |||
Line 3: | Line 3: | ||
==Solution 1== | ==Solution 1== | ||
+ | |||
By the Chicken McNugget theorem, the least possible value of <math>n</math> such that <math>91</math> cents cannot be formed satisfies <math>5n - (5 + n) = 91 \implies n = 24</math>, so <math>n</math> must be at least <math>24</math>. | By the Chicken McNugget theorem, the least possible value of <math>n</math> such that <math>91</math> cents cannot be formed satisfies <math>5n - (5 + n) = 91 \implies n = 24</math>, so <math>n</math> must be at least <math>24</math>. | ||
Line 14: | Line 15: | ||
~Revision by [[User:emerald_block|emerald_block]] | ~Revision by [[User:emerald_block|emerald_block]] | ||
+ | |||
+ | ===Note on finding and testing potential pairs=== | ||
+ | |||
+ | In order to find potential <math>(n,n+1)</math> pairs, we simply test all combinations of <math>n</math> and <math>n+1</math> that sum to less than <math>4n</math> (so that <math>n\ge24</math>) to see if they produce an integer value of <math>n</math> when their sum is set to <math>96</math>. Note that, since <math>96</math> is divisible by <math>1</math>, <math>2</math>, <math>3</math>, and <math>4</math>, we must either use only <math>n</math> or only <math>n+1</math>, as otherwise, the sum is guaranteed to not be divisible by one of the numbers <math>2</math>, <math>3</math>, and <math>4</math>. | ||
+ | |||
+ | <math> | ||
+ | \begin{array}{c|c|c} | ||
+ | \text{Combination} & \text{Sum} & n\text{-value} \\ \hline | ||
+ | n,n,n,n & 4n & 24 \\ | ||
+ | n+1,n+1,n+1 & 3n+3 & 31 \\ | ||
+ | n,n,n & 3n & 32 \\ | ||
+ | n+1,n+1 & 2n+2 & 47 \\ | ||
+ | n,n & 2n & 48 \\ | ||
+ | n+1 & n+1 & 95 \\ | ||
+ | n & n & 96 \\ | ||
+ | \end{array} | ||
+ | </math> | ||
+ | |||
+ | To test whether a pair works, we simply check that, using the number <math>5</math> and the two numbers in the pair, it is impossible to form a sum of <math>91</math>, and it is possible to form sums of <math>92</math>, <math>93</math>, and <math>94</math>. (<math>95</math> can always be formed using only <math>5</math>s, and the pair is already able to form <math>96</math> because that was how it was found.) We simply need to reach the residues <math>2</math>, <math>3</math>, and <math>4</math><math>\pmod{5}</math> using only <math>n</math> and <math>n+1</math> without going over the number we are trying to form, while being unable to do so with the residue <math>1</math>. As stated in the above solution, the last two pairs are clearly too large to work. | ||
+ | |||
+ | <math> | ||
+ | \begin{array}{c|c|c|c|c} | ||
+ | \text{Pair} & \text{Not }91 & 92 & 93 & 94 \\ \hline | ||
+ | 24,25 & \checkmark & \checkmark & \checkmark & \checkmark \\ | ||
+ | 31,32 & \times & \checkmark & \checkmark & \checkmark \\ | ||
+ | 32,33 & \times & \checkmark & \checkmark & \checkmark \\ | ||
+ | 47,48 & \checkmark & \checkmark & \checkmark & \checkmark \\ | ||
+ | 48,49 & \checkmark & \times & \checkmark & \checkmark \\ | ||
+ | \end{array} | ||
+ | </math> | ||
+ | |||
+ | (Note that if a pair is unable to fulfill a single requirement, there is no need to check the rest.) | ||
+ | |||
+ | ~[[User:emerald_block|emerald_block]] | ||
==Solution 2== | ==Solution 2== | ||
Line 33: | Line 68: | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2019|n=II|num-b=13|num-a=15}} | {{AIME box|year=2019|n=II|num-b=13|num-a=15}} | ||
+ | [[Category: Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 20:01, 9 August 2020
Contents
Problem
Find the sum of all positive integers such that, given an unlimited supply of stamps of denominations and cents, cents is the greatest postage that cannot be formed.
Solution 1
By the Chicken McNugget theorem, the least possible value of such that cents cannot be formed satisfies , so must be at least .
For a value of to work, we must not only be unable to form the value , but we must also be able to form the values through , as with these five values, we can form any value greater than by using additional cent stamps.
Notice that we must form the value without forming the value . If we use any cent stamps when forming , we could simply remove one to get . This means that we must obtain the value using only stamps of denominations and .
Recalling that , we can easily figure out the working pairs that can used to obtain , as we can use at most stamps without going over. The potential sets are , and .
The last two obviously do not work, since they are too large to form the values through , and by a little testing, only and can form the necessary values, so . .
~Revision by emerald_block
Note on finding and testing potential pairs
In order to find potential pairs, we simply test all combinations of and that sum to less than (so that ) to see if they produce an integer value of when their sum is set to . Note that, since is divisible by , , , and , we must either use only or only , as otherwise, the sum is guaranteed to not be divisible by one of the numbers , , and .
To test whether a pair works, we simply check that, using the number and the two numbers in the pair, it is impossible to form a sum of , and it is possible to form sums of , , and . ( can always be formed using only s, and the pair is already able to form because that was how it was found.) We simply need to reach the residues , , and using only and without going over the number we are trying to form, while being unable to do so with the residue . As stated in the above solution, the last two pairs are clearly too large to work.
(Note that if a pair is unable to fulfill a single requirement, there is no need to check the rest.)
Solution 2
Notice that once we hit all residues , we'd be able to get any number greater (since we can continually add to each residue). Furthermore, since otherwise is obtainable (by repeatedly adding to either or ) Since the given numbers are , , and , we consider two cases: when and when is not that.
When , we can only hit all residues once we get to (since and only contribute more residue ). Looking at multiples of greater than with , we get . It's easy to check that this works. Furthermore, any greater than this does not work since isn't the largest unobtainable value (can be verified using Chicken McNugget Theorem).
Now, if , then we'd need to go up to until we can hit all residues since and create distinct residues . Checking for such gives and . It's easy to check that works, but does not (since is unobtainable). Furthermore, any greater than this does not work since isn't the largest unobtainable value in those cases (can be verified using Chicken McNugget Theorem). (Also note that in the case, the residue has will not be produced until while the case has already been produced, so the highest possible value that cannot be produced would not be a number equivalent to )
Since we've checked all residues , we can be sure that these are all the possible values of . Hence, the answer is . - ktong
Solution 3
Obviously . We see that the problem's condition is equivalent to: 96 is the smallest number that can be formed which is 1 mod 5, and 92, 93, 94 can be formed (95 can always be formed). Now divide this up into cases. If , then 91 can be formed by using and some 5's, so there are no solutions for this case. If , then 91 can be formed by using and some 5's, so there are no solutions for this case either.
For , is the smallest value that can be formed which is 1 mod 5, so and . We see that , , and , so does work. If , then the smallest value that can be formed which is 1 mod 5 is , so and . We see that and , but 92 cannot be formed, so there are no solutions for this case. If , then we can just ignore since it is a multiple of 5, meaning that the Chicken McNuggest theorem is a both necessary and sufficient condition, and it states that meaning and . Hence, the only two that work are and , so our answer is . -Stormersyle
See Also
2019 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
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.