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 "2025 AIME II Problems/Problem 8"
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
From an unlimited supply of 1-cent coins, 10-cent coins, and 25-cent coins, Silas wants to find a collection of coins that has a total value of <math>N</math> cents, where <math>N</math> is a positive integer. He uses the so-called greedy algorithm, successively choosing the coin of greatest value that does not cause the value of his collection to exceed <math>N.</math> For example, to get 42 cents, Silas will choose a 25-cent coin, then a 10-cent coin, then 7 1-cent coins. However, this collection of 9 coins uses more coins than necessary to get a total of 42 cents; indeed, choosing 4 10-cent coins and 2 1-cent coins achieves the same total value with only 6 coins. In general, the greedy algorithm succeeds for a given <math>N</math> if no other collection of 1-cent, 10-cent, and 25-cent coins gives a total value of <math>N</math> cents using strictly fewer coins than the collection given by the greedy algorithm. Find the number of values of <math>N</math> between <math>1</math> and <math>1000</math> inclusive for which the greedy algorithm succeeds.
+
From an unlimited supply of <math>1</math>-cent coins, <math>10</math>-cent coins, and <math>25</math>-cent coins, Silas wants to find a collection of coins that has a total value of <math>N</math> cents, where <math>N</math> is a positive integer. He uses the so-called <math>\textit{greedy algorithm}</math>, successively choosing the coin of greatest value that does not cause the value of his collection to exceed <math>N</math>. For example, to get <math>42</math> cents, Silas will choose a <math>25</math>-cent coin, then a <math>10</math>-cent coin, then <math>7</math> <math>1</math>-cent coins. However, this collection of <math>9</math> coins uses more coins than necessary to get a total of <math>42</math> cents; indeed, choosing <math>4</math> <math>10</math>-cent coins and <math>2</math> <math>1</math>-cent coins achieves the same total value with only <math>6</math> coins.
  
−
== Solution 1==
+
In general, the greedy algorithm succeeds for a given <math>N</math> if no other collection of <math>1</math>-cent, <math>10</math>-cent, and <math>25</math>-cent coins gives a total value of <math>N</math> cents using strictly fewer coins than the collection given by the greedy algorithm. Find the number of values of <math>N</math> between <math>1</math> and <math>1000</math> inclusive for which the greedy algorithm succeeds.
  
−
First, we note that everything N <= 25 works.
+
==Solution 1==
  
−
Starting from 25-29, the greedy algorithm will choose the 25 big coin and it won't cause any problems.  
+
We begin by noting that all values of <math>N \leq 25</math> work without issue.
  
−
From 30-34, The greedy algorithm will select the 25 coin with 5 1-cent to approach to 30, whilst the optimal solution is to use 3 10-cent. This problem would be resolved from 35-39, as the greedy can select 25 + 10-cent to match the optimal solution.  
+
Starting from <math>N = 25</math> to <math>29</math>, the greedy algorithm will select the <math>25</math>-cent coin, and no problem arises.
  
−
From 40-44, the same problem occurs again. The algorithm will choose 25 + 10 + 5*1 to approach 40, whilst it could be solved by using 4 * 10 cent.  
+
From <math>N = 30</math> to <math>34</math>, the greedy algorithm will select the <math>25</math>-cent coin along with <math>5</math> <math>1</math>-cent coins to reach a total of <math>30</math>, while the optimal solution would involve using <math>3</math> <math>10</math>-cent coins. This issue is resolved from <math>N = 35</math> to <math>39</math>, as the greedy algorithm can now select <math>25 + 10</math>-cent coins to match the optimal solution.
  
−
The problem occurs again from 55-59, where 50 + 5*1 is not as great as using 25 + 3 * 10, and it will be resolved at 60. 65-69 will have this problem bursted out again, as 25 * 2 + 10 + 5 1-cents is not as good as 25 + 4 * 10 to approach 65.
+
From <math>N = 40</math> to <math>44</math>, a similar problem occurs again. The greedy algorithm selects <math>25 + 10 + 5 \times 1</math>-cent coins to reach 40, while the optimal solution would use 4 <math>10</math>-cent coins.
  
−
We observe that the cycle is 25 numbers, and 10 of the 25 numbers in a cycle doesn't work. The cycle starts at 30, and the next cycle will start 25 later (55), then 80, ... until 980-1005 for the last cycle to count.  
+
The problem occurs again from <math>N = 55</math> to <math>59</math>, where <math>50 + 5 \times 1</math> is not as good as using <math>25 + 3 \times 10</math>, and it is resolved at <math>N = 60</math>. From <math>N = 65</math> to <math>69</math>, a similar issue arises, as <math>25 \times 2 + 10 + 5 \times 1</math> is not as optimal as <math>25 + 4 \times 10</math> to approach 65.
  
−
The full cycles number is (955-30)/25 + 1 = 38, each cycle has 10 problem numbers, where 38*10 = 380. The cycle of 980 to 1005 has the issue numbers of 980-984 and 990-994, where there are also 10 numbers.  
+
We observe that this issue repeats in cycles of <math>25</math> numbers, with <math>10</math> of the <math>25</math> numbers in each cycle not working. The cycle starts at <math>30</math>, and the next cycle will start <math>25</math> numbers later, at <math>55</math>, then <math>80</math>, and so on, continuing until <math>980</math>–<math>1005</math> for the last cycle.
  
−
Therefore, the unsuccessful counts from 1 to 1000 inclusive would be 390, and the desired answer is 1000 - unsuccessful counts = 1000 - 390 = 610.
+
The total number of cycles is given by:
  
−
(Feel free to make any edits on grammar, latex and formats)
+
<cmath>
 +
\frac{955 - 30}{25} + 1 = 38,
 +
</cmath>
  
−
~Mitsuihisashi14
+
and each cycle contains <math>10</math> problematic numbers. Therefore, the total number of problematic numbers is:
 +
 
 +
<cmath>
 +
38 \times 10 = 380.
 +
</cmath>
 +
 
 +
The cycle from <math>980</math> to <math>1005</math> has the problematic numbers from <math>980</math> to <math>984</math> and <math>990</math> to <math>994</math>, giving another <math>10</math> problematic numbers.
 +
 
 +
Thus, the total number of unsuccessful numbers from <math>1</math> to <math>1000</math> inclusive is <math>390</math>, and the desired count of successful numbers is:
 +
 
 +
<cmath>
 +
1000 - 390 = \boxed{610}.
 +
</cmath>
 +
 
 +
(Feel free to make any edits on grammar, <math>\LaTeX</math> and formatting.)
 +
 
 +
~ Mitsuihisashi14
 +
 
 +
~ Edited by [https://artofproblemsolving.com/wiki/index.php/User:Aoum aoum]
  
 
==See also==
 
==See also==

Latest revision as of 23:01, 24 February 2025

Problem

From an unlimited supply of $1$-cent coins, $10$-cent coins, and $25$-cent coins, Silas wants to find a collection of coins that has a total value of $N$ cents, where $N$ is a positive integer. He uses the so-called $\textit{greedy algorithm}$, successively choosing the coin of greatest value that does not cause the value of his collection to exceed $N$. For example, to get $42$ cents, Silas will choose a $25$-cent coin, then a $10$-cent coin, then $7$ $1$-cent coins. However, this collection of $9$ coins uses more coins than necessary to get a total of $42$ cents; indeed, choosing $4$ $10$-cent coins and $2$ $1$-cent coins achieves the same total value with only $6$ coins.

In general, the greedy algorithm succeeds for a given $N$ if no other collection of $1$-cent, $10$-cent, and $25$-cent coins gives a total value of $N$ cents using strictly fewer coins than the collection given by the greedy algorithm. Find the number of values of $N$ between $1$ and $1000$ inclusive for which the greedy algorithm succeeds.

Solution 1

We begin by noting that all values of $N \leq 25$ work without issue.

Starting from $N = 25$ to $29$, the greedy algorithm will select the $25$-cent coin, and no problem arises.

From $N = 30$ to $34$, the greedy algorithm will select the $25$-cent coin along with $5$ $1$-cent coins to reach a total of $30$, while the optimal solution would involve using $3$ $10$-cent coins. This issue is resolved from $N = 35$ to $39$, as the greedy algorithm can now select $25 + 10$-cent coins to match the optimal solution.

From $N = 40$ to $44$, a similar problem occurs again. The greedy algorithm selects $25 + 10 + 5 \times 1$-cent coins to reach 40, while the optimal solution would use 4 $10$-cent coins.

The problem occurs again from $N = 55$ to $59$, where $50 + 5 \times 1$ is not as good as using $25 + 3 \times 10$, and it is resolved at $N = 60$. From $N = 65$ to $69$, a similar issue arises, as $25 \times 2 + 10 + 5 \times 1$ is not as optimal as $25 + 4 \times 10$ to approach 65.

We observe that this issue repeats in cycles of $25$ numbers, with $10$ of the $25$ numbers in each cycle not working. The cycle starts at $30$, and the next cycle will start $25$ numbers later, at $55$, then $80$, and so on, continuing until $980$–$1005$ for the last cycle.

The total number of cycles is given by:

\[\frac{955 - 30}{25} + 1 = 38,\]

and each cycle contains $10$ problematic numbers. Therefore, the total number of problematic numbers is:

\[38 \times 10 = 380.\]

The cycle from $980$ to $1005$ has the problematic numbers from $980$ to $984$ and $990$ to $994$, giving another $10$ problematic numbers.

Thus, the total number of unsuccessful numbers from $1$ to $1000$ inclusive is $390$, and the desired count of successful numbers is:

\[1000 - 390 = \boxed{610}.\]

(Feel free to make any edits on grammar, $\LaTeX$ and formatting.)

~ Mitsuihisashi14

~ Edited by aoum

See also

2025 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 7 		Followed by
Problem 9
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=2025_AIME_II_Problems/Problem_8&oldid=243763"