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 "2022 AIME II Problems/Problem 14"
(→‎Correction for the correction:)
 
(39 intermediate revisions by 9 users not shown)
Line 3: Line 3:
 
For positive integers <math>a</math>, <math>b</math>, and <math>c</math> with <math>a < b < c</math>, consider collections of postage stamps in denominations <math>a</math>, <math>b</math>, and <math>c</math> cents that contain at least one stamp of each denomination. If there exists such a collection that contains sub-collections worth every whole number of cents up to <math>1000</math> cents, let <math>f(a, b, c)</math> be the minimum number of stamps in such a collection. Find the sum of the three least values of <math>c</math> such that <math>f(a, b, c) = 97</math> for some choice of <math>a</math> and <math>b</math>.
 
For positive integers <math>a</math>, <math>b</math>, and <math>c</math> with <math>a < b < c</math>, consider collections of postage stamps in denominations <math>a</math>, <math>b</math>, and <math>c</math> cents that contain at least one stamp of each denomination. If there exists such a collection that contains sub-collections worth every whole number of cents up to <math>1000</math> cents, let <math>f(a, b, c)</math> be the minimum number of stamps in such a collection. Find the sum of the three least values of <math>c</math> such that <math>f(a, b, c) = 97</math> for some choice of <math>a</math> and <math>b</math>.
  
−
==Solution 1==
+
==Solution==
  
−
Notice that we must have <math>a = 1</math>, or else <math>1</math> cent stamp cannot be represented. At least <math>b-1</math> numbers of <math>1</math> cent stamps are needed to represent the values less than <math>b</math>. Using at most <math>c-1</math> stamps of value <math>1</math> and <math>b</math>, it is able to have all the values from <math>1</math> to <math>c-1</math> cents. Plus <math>\lfloor \frac{999}{c} \rfloor</math> stamps of value <math>c</math>, every value up to <math>1000</math> is able to be represented. Therefore using <math>\lfloor \frac{999}{c} \rfloor</math> stamps of value <math>c</math>, <math>\lfloor \frac{c-1}{b} \rfloor</math> stamps of value <math>b</math>, and <math>b-1</math> stamps of value <math>1</math> all values up to <math>1000</math> are able to be represented in sub-collections, while minimizing the number of stamps.
+
Notice that we must have <math>a = 1</math>; otherwise <math>1</math> cent stamp cannot be represented. At least <math>b-1</math> numbers of <math>1</math> cent stamps are needed to represent the values less than <math>b</math>. Using at most <math>c-1</math> stamps of value <math>1</math> and <math>b</math>, it can have all the values from <math>1</math> to <math>c-1</math> cents. Plus <math>\lfloor \frac{999}{c} \rfloor</math> stamps of value <math>c</math>, every value up to <math>1000</math> can be represented.  
  
−
So, <math>f(a, b, c) = \lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1</math>
+
===Correction:===
  
−
<math>\lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1 = 97</math>
+
This should be <math>\lfloor \frac{1000}{c} \rfloor</math>. The current function breaks when <math>c \mid 1000</math> and <math>b \mid c</math>. Take <math>c = 200</math> and <math>b = 20</math>. Then, we have <math>\lfloor \frac{999}{200} \rfloor = 4</math> stamps of value 200, <math>\lfloor \frac{199}{20} \rfloor = 9</math> stamps of value b, and 19 stamps of value 1. The maximum such a collection can give is <math>200 \cdot 4 + 20 \cdot 9 +19 \cdot 1 = 999</math>, just shy of the needed 1000. As for the rest of solution, proceed similarly, except use <math>1000</math> instead of <math>999</math>.
  
−
We can get the answer by solving this equation.
+
Also, some explanation: <math>b-1</math> one cent stamps cover all residues module <math>b</math>. Having <math>\lfloor \frac{c-1}{b} \rfloor</math> stamps of value b covers all residue classes modulo <math>c</math>. Finally, we just need <math>\lfloor \frac{1000}{c} \rfloor</math> to cover everything up to 1000.
  
−
To be continued......
+
In addition, note that this function sometimes may not always minimize the number of stamps required. This is due to the fact that the stamps of value <math>b</math> and of value <math>1</math> have the capacity to cover values greater than or equal to <math>c</math> (which occurs when <math>c-1</math> has a remainder less than <math>b-1</math> when divided by <math>b</math>). Thus, in certain cases, not all <math>\lfloor \frac{1000}{c} \rfloor</math> stamps of value c may be necessary, because the stamps of value <math>b</math> and 1 can replace one <math>c</math>.
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Crazyvideogamez CrazyVideoGamez]
 +
 
 +
 
 +
====Correction for the correction and the original solution:====
 +
 
 +
Actually, <math>f(a, b, c) = b + \lceil \frac{c}{b} \rceil + \lceil \frac{1001-b \lceil \frac{c}{b} \rceil}{c} \rceil - 2</math>.
 +
 
 +
This could be obtained by solving the minimum of <math>A+B+C</math> for the system of inequalities <math>A \geq b-14</math>, <math>A+Bb \geq c</math>, and <math>A+Bb+Cc \geq 1000</math>, (Using the inequality adjustment method) where <math>A</math>, <math>B</math>, and <math>C</math> represent the number of <math>a</math>, <math>b</math>, and <math>c</math> postage stamps used. It is possible to get that <math>A=b-1</math>, <math>B=\lceil \frac{c}{b} \rceil-1</math>, <math>C=\lceil \frac{1001-b \lceil \frac{c}{b} \rceil}{c} \rceil</math>. <math>f(a,b,c)=A+B+C</math> yields the above.
 +
 
 +
Note that in <math>\text{Case } 2</math>, <math>c=88</math>, for the original solution <math>a=1</math>, <math>b=86</math>, <math>c=88</math>, <math>f(a,b,c)=96</math> if the above definition is used.
 +
 
 +
When <math>A=85</math>, <math>B=1</math>, and <math>C=10</math>, you can get a collection that satisfies the conditions of the problem. <math>A+B+C=96</math> here.
 +
 
 +
Note that using the correction does not change that the original <math>f(1,87,88)=97</math>.
 +
 
 +
Under the correction of the correction:
 +
 
 +
The actual solution could be achieved by using inequalities on the left and right of <math>f(a,b,c)</math> to get
 +
 
 +
<math>b+\frac{1001}{c}-3<f(a,b,c)<c+1+\frac{1001}{c}</math>.
 +
 
 +
Similar steps follow after substituting <math>f(a,b,c)=97</math>.
 +
 
 +
However, <math>f(1,7,11)=f(1,87,88)=f(1,87,89)=97</math>.
 +
 
 +
Therefore the answer is still <math>11+88+89=\boxed{188}</math>.
 +
 
 +
~eric-z
 +
 
 +
————————————————————————————————————
 +
 
 +
 
 +
Therefore using <math>\lfloor \frac{999}{c} \rfloor</math> stamps of value <math>c</math>, <math>\lfloor \frac{c-1}{b} \rfloor</math> stamps of value <math>b</math>, and <math>b-1</math> stamps of value <math>1</math>, all values up to <math>1000</math> can be represented in sub-collections, while minimizing the number of stamps.
 +
 
 +
So, <math>f(a, b, c) = \lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1</math>.
 +
 
 +
<math>\lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1 = 97</math>. We can get the answer by solving this equation.
 +
 
 +
<math>c > \lfloor \frac{c-1}{b} \rfloor + b-1</math>
 +
 
 +
<math>\frac{999}{c} + c > \lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1 = 97</math>
 +
 
 +
<math>c^2 - 97c + 999 > 0</math>, <math>c > 85.3</math> or <math>c < 11.7</math>
 +
 
 +
<math>\lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1 > \frac{999}{c}</math>
 +
 
 +
<math>97 > \frac{999}{c}</math>, <math>c>10.3</math>
 +
 
 +
<math>\text{Case } 1:</math> <math>10.3 < c < 11.7 \rightarrow c = 11 \rightarrow \lfloor \frac{999}{11} \rfloor + \lfloor \frac{10}{b} \rfloor + b-1 = 97</math>
 +
<math>\lfloor \frac{10}{b} \rfloor + b = 8</math>, <math>b=7</math>
 +
 
 +
<math>\text{Case } 2: c>85.3</math>
 +
 
 +
<math>c = 86 \rightarrow</math> <math>\lfloor \frac{999}{86} \rfloor + \lfloor \frac{85}{b} \rfloor + b-1 = 97</math>
 +
<math>\lfloor \frac{85}{b} \rfloor + b = 87</math>, <math>b=87 > c \rightarrow \text{no solution}</math>
 +
 
 +
<math>c = 87 \rightarrow</math> <math>\lfloor \frac{999}{87} \rfloor + \lfloor \frac{86}{b} \rfloor + b-1 = 97</math>
 +
<math>\lfloor \frac{86}{b} \rfloor + b = 87</math>, <math>b=86</math> or <math>1</math>. <math>\text{We cannot have }b=1 \text{ since it doesn't satisfy } a<b \text{, and note that if } b=86 \text{ we can have 10 coins of value } c, 1 \text{ of } b, \text{ and } 85</math> <math>\text{of } a \text{ for a total of 96 coins and still be able to make every value from 1 to 1000. Thus } c=87 \text{ yields no solution.}</math>
 +
 
 +
<math>c = 88 \rightarrow</math> <math>\lfloor \frac{999}{88} \rfloor + \lfloor \frac{87}{b} \rfloor + b-1 = 97</math>
 +
<math>\lfloor \frac{87}{b} \rfloor + b = 87</math>, <math>b=86</math>
 +
 
 +
<math>c = 89 \rightarrow</math> <math>\lfloor \frac{999}{89} \rfloor + \lfloor \frac{88}{b} \rfloor + b-1 = 97</math>
 +
<math>\lfloor \frac{88}{b} \rfloor + b = 87</math>, <math>b=86</math>
 +
 
 +
The <math>3</math> least values of <math>c</math> are <math>11</math>, <math>88</math>, <math>89</math>. <math>11 + 88+ 89 = \boxed{\textbf{188}}</math>
  
 
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
~edited by bobjoebilly
 +
 +
==Video Solution==
 +
https://youtu.be/jptMMVCuj34
 +
 +
~MathProblemSolvingSkills.com
 +
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2022|n=II|num-b=13|num-a=15}}
 
{{AIME box|year=2022|n=II|num-b=13|num-a=15}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 22:46, 12 September 2024

Problem

For positive integers $a$, $b$, and $c$ with $a < b < c$, consider collections of postage stamps in denominations $a$, $b$, and $c$ cents that contain at least one stamp of each denomination. If there exists such a collection that contains sub-collections worth every whole number of cents up to $1000$ cents, let $f(a, b, c)$ be the minimum number of stamps in such a collection. Find the sum of the three least values of $c$ such that $f(a, b, c) = 97$ for some choice of $a$ and $b$.

Solution

Notice that we must have $a = 1$; otherwise $1$ cent stamp cannot be represented. At least $b-1$ numbers of $1$ cent stamps are needed to represent the values less than $b$. Using at most $c-1$ stamps of value $1$ and $b$, it can have all the values from $1$ to $c-1$ cents. Plus $\lfloor \frac{999}{c} \rfloor$ stamps of value $c$, every value up to $1000$ can be represented.

Correction:

This should be $\lfloor \frac{1000}{c} \rfloor$. The current function breaks when $c \mid 1000$ and $b \mid c$. Take $c = 200$ and $b = 20$. Then, we have $\lfloor \frac{999}{200} \rfloor = 4$ stamps of value 200, $\lfloor \frac{199}{20} \rfloor = 9$ stamps of value b, and 19 stamps of value 1. The maximum such a collection can give is $200 \cdot 4 + 20 \cdot 9 +19 \cdot 1 = 999$, just shy of the needed 1000. As for the rest of solution, proceed similarly, except use $1000$ instead of $999$.

Also, some explanation: $b-1$ one cent stamps cover all residues module $b$. Having $\lfloor \frac{c-1}{b} \rfloor$ stamps of value b covers all residue classes modulo $c$. Finally, we just need $\lfloor \frac{1000}{c} \rfloor$ to cover everything up to 1000.

In addition, note that this function sometimes may not always minimize the number of stamps required. This is due to the fact that the stamps of value $b$ and of value $1$ have the capacity to cover values greater than or equal to $c$ (which occurs when $c-1$ has a remainder less than $b-1$ when divided by $b$). Thus, in certain cases, not all $\lfloor \frac{1000}{c} \rfloor$ stamps of value c may be necessary, because the stamps of value $b$ and 1 can replace one $c$.

~CrazyVideoGamez


Correction for the correction and the original solution:

Actually, $f(a, b, c) = b + \lceil \frac{c}{b} \rceil + \lceil \frac{1001-b \lceil \frac{c}{b} \rceil}{c} \rceil - 2$.

This could be obtained by solving the minimum of $A+B+C$ for the system of inequalities $A \geq b-14$, $A+Bb \geq c$, and $A+Bb+Cc \geq 1000$, (Using the inequality adjustment method) where $A$, $B$, and $C$ represent the number of $a$, $b$, and $c$ postage stamps used. It is possible to get that $A=b-1$, $B=\lceil \frac{c}{b} \rceil-1$, $C=\lceil \frac{1001-b \lceil \frac{c}{b} \rceil}{c} \rceil$. $f(a,b,c)=A+B+C$ yields the above.

Note that in $\text{Case } 2$, $c=88$, for the original solution $a=1$, $b=86$, $c=88$, $f(a,b,c)=96$ if the above definition is used.

When $A=85$, $B=1$, and $C=10$, you can get a collection that satisfies the conditions of the problem. $A+B+C=96$ here.

Note that using the correction does not change that the original $f(1,87,88)=97$.

Under the correction of the correction:

The actual solution could be achieved by using inequalities on the left and right of $f(a,b,c)$ to get

$b+\frac{1001}{c}-3<f(a,b,c)<c+1+\frac{1001}{c}$.

Similar steps follow after substituting $f(a,b,c)=97$.

However, $f(1,7,11)=f(1,87,88)=f(1,87,89)=97$.

Therefore the answer is still $11+88+89=\boxed{188}$.

~eric-z

————————————————————————————————————


Therefore using $\lfloor \frac{999}{c} \rfloor$ stamps of value $c$, $\lfloor \frac{c-1}{b} \rfloor$ stamps of value $b$, and $b-1$ stamps of value $1$, all values up to $1000$ can be represented in sub-collections, while minimizing the number of stamps.

So, $f(a, b, c) = \lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1$.

$\lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1 = 97$. We can get the answer by solving this equation.

$c > \lfloor \frac{c-1}{b} \rfloor + b-1$

$\frac{999}{c} + c > \lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1 = 97$

$c^2 - 97c + 999 > 0$, $c > 85.3$ or $c < 11.7$

$\lfloor \frac{999}{c} \rfloor + \lfloor \frac{c-1}{b} \rfloor + b-1 > \frac{999}{c}$

$97 > \frac{999}{c}$, $c>10.3$ 

$\text{Case } 1:$ $10.3 < c < 11.7 \rightarrow c = 11 \rightarrow \lfloor \frac{999}{11} \rfloor + \lfloor \frac{10}{b} \rfloor + b-1 = 97$
$\lfloor \frac{10}{b} \rfloor + b = 8$, $b=7$

$\text{Case } 2: c>85.3$

$c = 86 \rightarrow$ $\lfloor \frac{999}{86} \rfloor + \lfloor \frac{85}{b} \rfloor + b-1 = 97$
$\lfloor \frac{85}{b} \rfloor + b = 87$, $b=87 > c \rightarrow \text{no solution}$

$c = 87 \rightarrow$ $\lfloor \frac{999}{87} \rfloor + \lfloor \frac{86}{b} \rfloor + b-1 = 97$
$\lfloor \frac{86}{b} \rfloor + b = 87$, $b=86$ or $1$. $\text{We cannot have }b=1 \text{ since it doesn't satisfy } a<b \text{, and note that if } b=86 \text{ we can have 10 coins of value } c, 1 \text{ of } b, \text{ and } 85$ $\text{of } a \text{ for a total of 96 coins and still be able to make every value from 1 to 1000. Thus } c=87 \text{ yields no solution.}$

$c = 88 \rightarrow$ $\lfloor \frac{999}{88} \rfloor + \lfloor \frac{87}{b} \rfloor + b-1 = 97$
$\lfloor \frac{87}{b} \rfloor + b = 87$, $b=86$

$c = 89 \rightarrow$ $\lfloor \frac{999}{89} \rfloor + \lfloor \frac{88}{b} \rfloor + b-1 = 97$
$\lfloor \frac{88}{b} \rfloor + b = 87$, $b=86$

The $3$ least values of $c$ are $11$, $88$, $89$. $11 + 88+ 89 = \boxed{\textbf{188}}$

~isabelchen ~edited by bobjoebilly

Video Solution

https://youtu.be/jptMMVCuj34

~MathProblemSolvingSkills.com


See Also

2022 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=2022_AIME_II_Problems/Problem_14&oldid=227087"