Difference between revisions of "2019 AIME II Problems/Problem 14"
(deleted troll solution) |
(revised solution) |
||
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 | + | 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>. |
+ | |||
+ | For a value of <math>n</math> to work, we must not only be unable to form the value <math>91</math>, but we must also be able to form the values <math>92</math> through <math>96</math>, as with these five values, we can form any value greater than <math>96</math> by using additional <math>5</math> cent stamps. | ||
+ | |||
+ | Notice that we must form the value <math>96</math> without forming the value <math>91</math>. If we use any <math>5</math> cent stamps when forming <math>96</math>, we could simply remove one to get <math>91</math>. This means that we must obtain the value <math>96</math> using only stamps of denominations <math>n</math> and <math>n+1</math>. | ||
+ | |||
+ | Recalling that <math>n \geq 24</math>, we can easily figure out the working <math>(n,n+1)</math> pairs that can used to obtain <math>96</math>, as we can use at most <math>\frac{96}{24}=4</math> stamps without going over. The potential sets are <math>(24, 25), (31, 32), (32, 33), (47, 48), (48, 49), (95, 96)</math>, and <math>(96, 97)</math>. | ||
+ | |||
+ | The last two obviously do not work, since they are too large to form the values <math>92</math> through <math>94</math>, and by a little testing, only <math>(24, 25)</math> and <math>(47, 48)</math> can form the necessary values, so <math>n \in \{24, 47\}</math>. <math>24 + 47 = \boxed{071}</math>. | ||
+ | |||
+ | ~Revision by [[User:emerald_block|emerald_block]] | ||
==Solution 2== | ==Solution 2== |
Revision as of 16:42, 5 June 2020
Contents
[hide]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
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.