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 - 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 \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 17:42, 5 June 2020

Problem

Find the sum of all positive integers $n$ such that, given an unlimited supply of stamps of denominations $5,n,$ and $n+1$ cents, $91$ cents is the greatest postage that cannot be formed.

Solution 1

By the Chicken McNugget theorem, the least possible value of $n$ such that $91$ cents cannot be formed satisfies $5n - (5 + n) = 91 \implies n = 24$, so $n$ must be at least $24$.

For a value of $n$ to work, we must not only be unable to form the value $91$, but we must also be able to form the values $92$ through $96$, as with these five values, we can form any value greater than $96$ by using additional $5$ cent stamps.

Notice that we must form the value $96$ without forming the value $91$. If we use any $5$ cent stamps when forming $96$, we could simply remove one to get $91$. This means that we must obtain the value $96$ using only stamps of denominations $n$ and $n+1$.

Recalling that $n \geq 24$, we can easily figure out the working $(n,n+1)$ pairs that can used to obtain $96$, as we can use at most $\frac{96}{24}=4$ stamps without going over. The potential sets are $(24, 25), (31, 32), (32, 33), (47, 48), (48, 49), (95, 96)$, and $(96, 97)$.

The last two obviously do not work, since they are too large to form the values $92$ through $94$, and by a little testing, only $(24, 25)$ and $(47, 48)$ can form the necessary values, so $n \in \{24, 47\}$. $24 + 47 = \boxed{071}$.

~Revision by emerald_block

Solution 2

Notice that once we hit all residues $\bmod 5$, we'd be able to get any number greater (since we can continually add $5$ to each residue). Furthermore, $n\not\equiv 0,1\pmod{5}$ since otherwise $91$ is obtainable (by repeatedly adding $5$ to either $n$ or $n+1$) Since the given numbers are $5$, $n$, and $n+1$, we consider two cases: when $n\equiv 4\pmod{5}$ and when $n$ is not that.

When $n\equiv 4 \pmod{5}$, we can only hit all residues $\bmod 5$ once we get to $4n$ (since $n$ and $n+1$ only contribute $1$ more residue $\bmod 5$). Looking at multiples of $4$ greater than $91$ with $n\equiv 4\pmod{5}$, we get $n=24$. It's easy to check that this works. Furthermore, any $n$ greater than this does not work since $91$ isn't the largest unobtainable value (can be verified using Chicken McNugget Theorem).

Now, if $n\equiv 2,3\pmod{5}$, then we'd need to go up to $2(n+1)=2n+2$ until we can hit all residues $\bmod 5$ since $n$ and $n+1$ create $2$ distinct residues $\bmod{5}$. Checking for such $n$ gives $n=47$ and $n=48$. It's easy to check that $n=47$ works, but $n=48$ does not (since $92$ is unobtainable). Furthermore, any $n$ greater than this does not work since $91$ isn't the largest unobtainable value in those cases (can be verified using Chicken McNugget Theorem). (Also note that in the $3 \pmod{5}$ case, the residue $2 \pmod{5}$ has will not be produced until $3(n+1)$ while the $1\pmod5$ case has already been produced, so the highest possible value that cannot be produced would not be a number equivalent to $1 \pmod5$)

Since we've checked all residues $\bmod 5$, we can be sure that these are all the possible values of $n$. Hence, the answer is $24+47=\boxed{071}$. - ktong

Solution 3

Obviously $n\le 90$. 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 $n\equiv 0\pmod{5}$, then 91 can be formed by using $n+1$ and some 5's, so there are no solutions for this case. If $n\equiv 1\pmod{5}$, then 91 can be formed by using $n$ and some 5's, so there are no solutions for this case either.

For $n\equiv 2\pmod{5}$, $2n+2$ is the smallest value that can be formed which is 1 mod 5, so $2n+2=96$ and $n=47$. We see that $92=45+47$, $93=48+45$, and $94=47+47$, so $n=47$ does work. If $n\equiv 3\pmod{5}$, then the smallest value that can be formed which is 1 mod 5 is $2n$, so $2n=96$ and $n=48$. We see that $94=49+45$ and $93=48+45$, but 92 cannot be formed, so there are no solutions for this case. If $n\equiv 4\pmod{5}$, then we can just ignore $n+1$ since it is a multiple of 5, meaning that the Chicken McNuggest theorem is a both necessary and sufficient condition, and it states that $5n-n-5=91$ meaning $4n=96$ and $n=24$. Hence, the only two $n$ that work are $n=24$ and $n=47$, so our answer is $24+47=\boxed{071}$. -Stormersyle

See Also

2019 AIME II (ProblemsAnswer KeyResources)
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. AMC logo.png