Difference between revisions of "2019 AIME II Problems/Problem 14"
m (→Solution) |
(→Solution) |
||
Line 2: | Line 2: | ||
Find the sum of all positive integers <math>n</math> such that, given an unlimited supply of stamps of denominations <math>5,n,</math> and <math>n+1</math> cents, <math>91</math> cents is the greatest postage that cannot be formed. | Find the sum of all positive integers <math>n</math> such that, given an unlimited supply of stamps of denominations <math>5,n,</math> and <math>n+1</math> cents, <math>91</math> cents is the greatest postage that cannot be formed. | ||
− | ==Solution== | + | ==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</math>, so <math>n = 24</math>. For values of <math>n</math> greater than <math>24</math>, notice that if <math>91</math> cents cannot be formed, then any number <math>1 \bmod 5</math> less than <math>91</math> also cannot be formed. The proof of this is that if any number <math>1 \bmod 5</math> less than <math>91</math> can be formed, then we could keep adding <math>5</math> cent stamps until we reach <math>91</math> cents. However, since <math>91</math> cents is the greatest postage that cannot be formed, <math>96</math> cents is the first number that is <math>1 \bmod 5</math> that can be formed, so it must be formed without any <math>5</math> cent stamps. There are few <math>(n, n + 1)</math> pairs, where <math>n \geq 24</math>, that can make <math>96</math> cents. These are cases where one of <math>n</math> and <math>n + 1</math> is a factor of <math>96</math>, which 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 <math>92</math> through <math>94</math> cents also cannot be formed, and by a little testing, only <math>(24, 25)</math> and <math>(47, 48)</math> satisfy the condition that <math>91</math> cents is the greatest postage that cannot be formed, so <math>n = 24, 47</math>. <math>24 + 47 = \boxed{071}</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</math>, so <math>n = 24</math>. For values of <math>n</math> greater than <math>24</math>, notice that if <math>91</math> cents cannot be formed, then any number <math>1 \bmod 5</math> less than <math>91</math> also cannot be formed. The proof of this is that if any number <math>1 \bmod 5</math> less than <math>91</math> can be formed, then we could keep adding <math>5</math> cent stamps until we reach <math>91</math> cents. However, since <math>91</math> cents is the greatest postage that cannot be formed, <math>96</math> cents is the first number that is <math>1 \bmod 5</math> that can be formed, so it must be formed without any <math>5</math> cent stamps. There are few <math>(n, n + 1)</math> pairs, where <math>n \geq 24</math>, that can make <math>96</math> cents. These are cases where one of <math>n</math> and <math>n + 1</math> is a factor of <math>96</math>, which 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 <math>92</math> through <math>94</math> cents also cannot be formed, and by a little testing, only <math>(24, 25)</math> and <math>(47, 48)</math> satisfy the condition that <math>91</math> cents is the greatest postage that cannot be formed, so <math>n = 24, 47</math>. <math>24 + 47 = \boxed{071}</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | Notice that once we hit all residues <math>\bmod 5</math>, we'd be able to get any number greater (since we can continually add <math>5</math> to each residue). Furthermore, <math>n\not\equiv 0,1\pmod{5}</math> since otherwise <math>91</math> is obtainable (by repeatedly adding <math>5</math> to either <math>n</math> or <math>n+1</math>) Since the given numbers are <math>5</math>, <math>n</math>, and <math>n+1</math>, we consider two cases: when <math>n\equiv 4\pmod{5}</math> and when <math>n</math> is not that. | ||
+ | |||
+ | When <math>n\equiv 4 \pmod{5}</math>, we can only hit all residues <math>\bmod 5</math> once we get to <math>4n</math>. Looking at multiples of <math>4</math> greater than <math>91</math> with <math>n\equiv 4\text{ or }1 \pmod{5}</math>, we get <math>n=24</math>. It's easy to check that this works. Furthermore, any <math>n</math> greater than this does not work since <math>91</math> isn't the largest unobtainable value (can be verified using Chicken McNugget Theorem). | ||
+ | |||
+ | Now, if <math>n\equiv 2,3\pmod{5}</math>, then we'd need to go up to <math>2(n+1)=2n+2</math> until we can hit all residues <math>\bmod 5</math> since <math>n</math> and <math>n+1</math> create <math>2</math> distinct residues <math>\bmod{5}</math>. Checking for such <math>n</math> gives <math>n=47</math> and <math>n=48</math>. It's easy to check that <math>n=47</math> works, but <math>n=48</math> does not (since <math>92</math> is unobtainable). Furthermore, any <math>n</math> greater than this does not work since <math>91</math> isn't the largest unobtainable value in those cases (can be verified using Chicken McNugget Theorem). | ||
+ | |||
+ | Since we've checked all residues <math>\bmod 5</math>, we can be sure that these are all the possible values of <math>n</math>. Hence, the answer is <math>24+47=\boxed{071}</math>. - ktong | ||
==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}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 23:38, 22 March 2019
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
. For values of
greater than
, notice that if
cents cannot be formed, then any number
less than
also cannot be formed. The proof of this is that if any number
less than
can be formed, then we could keep adding
cent stamps until we reach
cents. However, since
cents is the greatest postage that cannot be formed,
cents is the first number that is
that can be formed, so it must be formed without any
cent stamps. There are few
pairs, where
, that can make
cents. These are cases where one of
and
is a factor of
, which are
, and
. The last two obviously do not work since
through
cents also cannot be formed, and by a little testing, only
and
satisfy the condition that
cents is the greatest postage that cannot be formed, so
.
.
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
. 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).
Since we've checked all residues , we can be sure that these are all the possible values of
. Hence, the answer is
. - ktong
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.