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

2025 AIME II Problems/Problem 8

Revision as of 22:32, 13 February 2025 by Mitsuihisashi14 (talk | contribs) (→‎Solution)

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

First, we note that everything N <= 25 works.

Starting from 25-29, the greedy algorithm will choose the 25 big coin and it won't cause any problems.

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 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.

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.

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 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.

Therefore, the unsuccessful counts from 1 to 1000 inclusive would be 390, and the desired answer is 1000 - unsuccessful counts = 1000 - 390 = 610.

(Feel free to make any edits on grammar, latex and formats)

~Mitsuihisashi14

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_AIME_II_Problems/Problem_8&oldid=242411"