Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (fixed mistake in text)
(→‎Solution 3)
 
(10 intermediate revisions by 6 users not shown)
Line 12: Line 12:
 
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>.
 
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>.
+
The last two obviously do not work, since they are too large to form the values <math>92</math> through <math>95</math>. 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]]
+
~Revision by [[User:emerald_block|emerald_block]] ~Minor Revision by [[Mathkiddie|Mathkiddie]]
  
 
===Note on finding and testing potential pairs===
 
===Note on finding and testing potential pairs===
Line 33: Line 33:
 
</math>
 
</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 that 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.
+
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>
 
<math>
Line 62: Line 62:
 
Obviously <math>n\le 90</math>. 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 <math>n\equiv 0\pmod{5}</math>, then 91 can be formed by using <math>n+1</math> and some 5's, so there are no solutions for this case. If <math>n\equiv 1\pmod{5}</math>, then 91 can be formed by using <math>n</math> and some 5's, so there are no solutions for this case either.
 
Obviously <math>n\le 90</math>. 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 <math>n\equiv 0\pmod{5}</math>, then 91 can be formed by using <math>n+1</math> and some 5's, so there are no solutions for this case. If <math>n\equiv 1\pmod{5}</math>, then 91 can be formed by using <math>n</math> and some 5's, so there are no solutions for this case either.
  
−
For <math>n\equiv 2\pmod{5}</math>, <math>2n+2</math> is the smallest value that can be formed which is 1 mod 5, so <math>2n+2=96</math> and <math>n=47</math>. We see that <math>92=45+47</math>, <math>93=48+45</math>, and <math>94=47+47</math>, so <math>n=47</math> does work. If <math>n\equiv 3\pmod{5}</math>, then the smallest value that can be formed which is 1 mod 5 is <math>2n</math>, so <math>2n=96</math> and <math>n=48</math>. We see that <math>94=49+45</math> and <math>93=48+45</math>, but 92 cannot be formed, so there are no solutions for this case. If <math>n\equiv 4\pmod{5}</math>, then we can just ignore <math>n+1</math> since it is a multiple of 5, meaning that the Chicken McNuggest theorem is a both necessary and sufficient condition, and it states that <math>5n-n-5=91</math> meaning <math>4n=96</math> and <math>n=24</math>.
+
For <math>n\equiv 2\pmod{5}</math>, <math>2n+2</math> is the smallest value that can be formed which is 1 mod 5, so <math>2n+2=96</math> and <math>n=47</math>. We see that <math>92=45+47</math>, <math>93=48+45</math>, and <math>94=47+47</math>, so <math>n=47</math> does work. If <math>n\equiv 3\pmod{5}</math>, then the smallest value that can be formed which is 1 mod 5 is <math>2n</math>, so <math>2n=96</math> and <math>n=48</math>. We see that <math>94=49+45</math> and <math>93=48+45</math>, but 92 cannot be formed, so there are no solutions for this case. If <math>n\equiv 4\pmod{5}</math>, then we can just ignore <math>n+1</math> since it is a multiple of 5, meaning that the Chicken McNugget theorem is a both necessary and sufficient condition, and it states that <math>5n-n-5=91</math> meaning <math>4n=96</math> and <math>n=24</math>.
 
Hence, the only two <math>n</math> that work are <math>n=24</math> and <math>n=47</math>, so our answer is <math>24+47=\boxed{071}</math>.
 
Hence, the only two <math>n</math> that work are <math>n=24</math> and <math>n=47</math>, so our answer is <math>24+47=\boxed{071}</math>.
 
-Stormersyle
 
-Stormersyle
 +
 +
==Solution 4 (straightforward)==
 +
 +
Consider a postage that gives <math>96</math>. We cannot use a <math>5</math>-stamp as otherwise simply removing it yields a postage that gives <math>91</math>. Additionally, there cannot be at least <math>5</math> of <math>n</math>-stamps or <math>n + 1</math>-stamps, as else we can convert <math>5</math> of the same valued stamp into a positive number of <math>5</math>-stamps, then remove one to get a postage of <math>91</math>.
 +
 +
 +
From here consider integers <math>0 \le a, b, \le 4</math> where <math>an + b(n + 1) = 96 \implies n = \dfrac{96 - b}{a + b}</math>. The only pairs <math>(a, b)</math> that yield an integer value are <math>(a, b) = (0, 2), (0, 3), (0, 4), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1)</math> which generate the values <math>n = 47, 31, 23, 96, 48, 32, 24, 19</math> respectively. It is easy to find counterexamples of postages that evaluate to <math>91</math> besides <math>n = 24, 47</math>.
 +
 +
 +
Now for <math>n = 24</math> clearly <math>91</math> is unobtainable since we need a <math>4 \pmod {5}</math> amount of <math>24</math>-stamps which exceeds a value of <math>96</math>. A similar result holds for <math>n = 47</math> as any evaluation <math>\le 2 \cdot 47</math> can only be <math>0, 2, 3 \pmod{5}</math>. In both cases it is easy to construct a postage for <math>92, 93, 94, 95, 96</math>, to which repeatedly adding <math>5</math>-stamps makes all postages worth <math>>91</math> possible. The requesteed sum is <math>24 + 47 = \boxed{71}</math>.
 +
 +
- blueprimes
 +
 +
==Video Solution==
 +
Video solution by Dr. Osman Nal: https://www.youtube.com/watch?v=fTZP2e-_rjA
 +
 +
~Mathkiddie
  
 
==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 22:26, 22 November 2024

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 $95$. 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 ~Minor Revision by Mathkiddie

Note on finding and testing potential pairs

In order to find potential $(n,n+1)$ pairs, we simply test all combinations of $n$ and $n+1$ that sum to less than $4n$ (so that $n\ge24$) to see if they produce an integer value of $n$ when their sum is set to $96$. Note that, since $96$ is divisible by $1$, $2$, $3$, and $4$, we must either use only $n$ or only $n+1$, as otherwise, the sum is guaranteed to not be divisible by one of the numbers $2$, $3$, and $4$.

$\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}$

To test whether a pair works, we simply check that, using the number $5$ and the two numbers in the pair, it is impossible to form a sum of $91$, and it is possible to form sums of $92$, $93$, and $94$. ($95$ can always be formed using only $5$s, and the pair is already able to form $96$ because that was how it was found.) We simply need to reach the residues $2$, $3$, and $4$$\pmod{5}$ using only $n$ and $n+1$ without going over the number we are trying to form, while being unable to do so with the residue $1$. As stated in the above solution, the last two pairs are clearly too large to work.

$\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}$

(Note that if a pair is unable to fulfill a single requirement, there is no need to check the rest.)

~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 McNugget 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

Solution 4 (straightforward)

Consider a postage that gives $96$. We cannot use a $5$-stamp as otherwise simply removing it yields a postage that gives $91$. Additionally, there cannot be at least $5$ of $n$-stamps or $n + 1$-stamps, as else we can convert $5$ of the same valued stamp into a positive number of $5$-stamps, then remove one to get a postage of $91$.


From here consider integers $0 \le a, b, \le 4$ where $an + b(n + 1) = 96 \implies n = \dfrac{96 - b}{a + b}$. The only pairs $(a, b)$ that yield an integer value are $(a, b) = (0, 2), (0, 3), (0, 4), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1)$ which generate the values $n = 47, 31, 23, 96, 48, 32, 24, 19$ respectively. It is easy to find counterexamples of postages that evaluate to $91$ besides $n = 24, 47$.


Now for $n = 24$ clearly $91$ is unobtainable since we need a $4 \pmod {5}$ amount of $24$-stamps which exceeds a value of $96$. A similar result holds for $n = 47$ as any evaluation $\le 2 \cdot 47$ can only be $0, 2, 3 \pmod{5}$. In both cases it is easy to construct a postage for $92, 93, 94, 95, 96$, to which repeatedly adding $5$-stamps makes all postages worth $>91$ possible. The requesteed sum is $24 + 47 = \boxed{71}$.

- blueprimes

Video Solution

Video solution by Dr. Osman Nal: https://www.youtube.com/watch?v=fTZP2e-_rjA

~Mathkiddie

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_II_Problems/Problem_14&oldid=235318"