Difference between revisions of "2019 AIME II Problems/Problem 14"

Revision as of 18:13, 26 February 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$ , so $n = 24$ . For values of $n$ greater than $24$ , notice that if $91$ cents cannot be formed, then any number $1 \bmod 5$ less than $91$ also cannot be formed. The proof of this is that if any number $1 \bmod 5$ less than $91$ can be formed, then we could keep adding $5$ cent stamps until we reach $91$ cents. However, since $91$ cents is the greatest postage that cannot be formed, $96$ cents is the first number that is $1 \bmod 5$ that can be formed, so it must be formed without any $5$ cent stamps. There are few $(n, n + 1)$ pairs, where $n \geq 24$ , that can make $96$ cents. These are cases where one of $n$ and $n + 1$ is a factor of $96$ , which are $(24, 25), (31, 32), (32, 33), (47, 48), (48, 49), (95, 96)$ , and $(96, 97)$ . The last two obviously do not work since $92$ through $94$ cents also cannot be formed, and by a little testing, only $(24, 25)$ and $(47, 48)$ satisfy the condition that $91$ cents is the greatest postage that cannot be formed, so $n = 24, 47$ . $24 + 47 = \boxed{071}$ .

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

@@ Line 10: / Line 10: @@
 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> (since <math>n</math> and <math>n+1</math> only contribute <math>1</math> more residue <math>\bmod 5</math>). Looking at multiples of <math>4</math> greater than <math>91</math> with <math>n\equiv 4\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). (Also note that in the <math>3 \pmod{5}</math> case, the residue <math>2 \pmod{5}</math> has not been produced while the <math>1\bmod5</math> case has already been produced, so the highest possible value that cannot be produced would not be a number equivalent to <math>1 \pmod5</math>)
+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). (Also note that in the <math>3 \pmod{5}</math> case, the residue <math>2 \pmod{5}</math> has will not be produced until <math>3(n+1)</math> while the <math>1\pmod5</math> case has already been produced, so the highest possible value that cannot be produced would not be a number equivalent to <math>1 \pmod5</math>)
 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

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

Page

Toolbox

Search