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"

m (→‎Solution 1)
 
(2 intermediate revisions by the same user 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.
 +
 
 +
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.
  
 
==Solution 1==
 
==Solution 1==
Line 6: Line 8:
 
We begin by noting that all values of <math>N \leq 25</math> work without issue.
 
We begin by noting that all values of <math>N \leq 25</math> work without issue.
  
−
Starting from <math>N = 25</math> to <math>29</math>, the greedy algorithm will select the 25-cent coin, and no problem arises.
+
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 <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 <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.
  
 
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.
 
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.
Line 14: Line 16:
 
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 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 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.
+
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.
  
 
The total number of cycles is given by:
 
The total number of cycles is given by:
Line 22: Line 24:
 
</cmath>
 
</cmath>
  
−
and each cycle contains 10 problematic numbers. Therefore, the total number of problematic numbers is:
+
and each cycle contains <math>10</math> problematic numbers. Therefore, the total number of problematic numbers is:
  
 
<cmath>
 
<cmath>
Line 28: Line 30:
 
</cmath>
 
</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.
+
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 1 to 1000 inclusive is <math>390</math>, and the desired count of successful numbers is:
+
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>
 
<cmath>

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"