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"
(→‎Solution 1)
Line 2: Line 2:
 
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 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.
  
−
== Solution 1==
+
==Solution 1==
  
−
First, we note that everything N <= 25 works.
+
We begin by noting that all values of <math>N \leq 25</math> work without issue.
  
−
Starting from 25-29, the greedy algorithm will choose the 25 big coin and it won't cause any problems.  
+
Starting from <math>N = 25</math> to <math>29</math>, the greedy algorithm will select the 25-cent coin, and no problem arises.
  
−
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.  
+
From <math>N = 30</math> to <math>34</math>, 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 <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.
  
−
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 = 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.
  
−
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.
+
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.
  
−
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.  
+
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 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.
+
The total number of cycles is given by:
  
−
Therefore, the unsuccessful counts from 1 to 1000 inclusive would be 390, and the desired answer is 1000 - unsuccessful counts = 1000 - 390 = 610.
+
<cmath>
 +
\frac{955 - 30}{25} + 1 = 38,
 +
</cmath>
  
−
(Feel free to make any edits on grammar, latex and formats)
+
and each cycle contains 10 problematic numbers. Therefore, the total number of problematic numbers is:
 +
 
 +
<cmath>
 +
38 \times 10 = 380.
 +
</cmath>
 +
 
 +
The cycle from 980 to 1005 has the problematic numbers from 980 to 984 and from 990 to 994, which gives another 10 problematic numbers.
 +
 
 +
Thus, the total number of unsuccessful numbers from 1 to 1000 inclusive is <math>390</math>, and the desired count of successful numbers is:
 +
 
 +
<cmath>
 +
1000 - 390 = 610.
 +
</cmath>
 +
 
 +
(Feel free to make any edits on grammar, <math>\LaTeX</math> and formatting.)
  
 
~Mitsuihisashi14
 
~Mitsuihisashi14
 +
 +
~ Edited by [https://artofproblemsolving.com/wiki/index.php/User:Aoum aoum]
  
 
==See also==
 
==See also==

Revision as of 16:48, 14 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 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 from 990 to 994, which gives 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 = 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=242586"