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 (→‎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

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$. Looking at multiples of $4$ greater than $91$ with $n\equiv 4\text{ or }1 \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).

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

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=104847"