Difference between revisions of "2025 AIME II Problems/Problem 8"

Latest revision as of 21:09, 15 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 = \boxed{610}.$

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

~ Mitsuihisashi14

~ Edited by aoum

@@ 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.
-== Solution ==
+==Solution 1==
+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.
+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 = 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 <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.
+The total number of cycles is given by:
+<cmath>
+\frac{955 - 30}{25} + 1 = 38,
+</cmath>
+and each cycle contains 10 problematic numbers. Therefore, the total number of problematic numbers is:
+<cmath>
+\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>
+- 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==
+{{AIME box|year=2025|num-b=7|num-a=9|n=II}}
+{{MAA Notice}}

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

Page

Toolbox

Search

Difference between revisions of "2025 AIME II Problems/Problem 8"

Latest revision as of 21:09, 15 February 2025

Problem

Solution 1

See also