Question

Con un suministro ilimitado de monedas de $1$ centavo, monedas de $10$ centavos y monedas de $25$ centavos, Silas quiere encontrar una colección de monedas que tenga un valor total de $N$ centavos, donde $N$ es un entero positivo. Usa el llamado algoritmo voraz, eligiendo sucesivamente la moneda de mayor valor que no haga que el valor de su colección supere $N.$ Por ejemplo, para obtener $42$ centavos, Silas elegirá una moneda de $25$ centavos, luego una de $10$ centavos, y luego $7$ monedas de $1$ centavo. Sin embargo, esta colección de $9$ monedas usa más monedas de las necesarias para obtener un total de $42$ centavos; en efecto, elegir $4$ monedas de $10$ centavos y $2$ monedas de $1$ centavo logra el mismo valor total con solo $6$ monedas.

En general, el algoritmo voraz tiene éxito para un $N$ dado si ninguna otra colección de monedas de $1$ centavo, $10$ centavos y $25$ centavos da un valor total de $N$ centavos usando estrictamente menos monedas que la colección dada por el algoritmo voraz. Halla la cantidad de valores de $N$ entre $1$ y $1000$ inclusive para los cuales el algoritmo voraz tiene éxito.

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.

Respuesta

Solución:

En cualquier colección óptima hay a lo sumo $9$ monedas de un centavo (diez de un centavo podrían convertirse en una de diez) y a lo sumo $4$ monedas de diez centavos (cinco de diez podrían convertirse en dos de veinticinco), así que sus monedas de diez y de un centavo valen a lo sumo $49$ centavos. Por lo tanto una colección óptima usa $q = \lfloor N/25 \rfloor$ monedas de veinticinco, como el algoritmo voraz, o $q - 1$ monedas de veinticinco. Para una cantidad $v$ formada solo por monedas de diez y de un centavo, el mejor conteo es $f(v) = \lfloor v/10 \rfloor + (v \bmod 10),$ que es lo que hace el algoritmo voraz con el residuo.

Sea $r = N \bmod 25.$ El algoritmo voraz usa $q + f(r)$ monedas, y el único rival usa $(q - 1) + f(r + 25)$ monedas (posible cuando $q \ge 1$ ), así que el algoritmo voraz falla exactamente cuando $f(r + 25) \le f(r).$ Tabulando: para $r = 0, \ldots, 4,$ $f(r+25) = r + 7 \gt f(r) = r;$ para $r = 5, \ldots, 9,$ $f(r+25) = r - 2 \le r;$ para $r = 10, \ldots, 14,$ $f(r+25) = r - 2 \gt r - 9;$ para $r = 15, \ldots, 19,$ $f(r+25) = r - 11 \le r - 9;$ para $r = 20, \ldots, 24,$ $f(r+25) = r - 11 \gt r - 18.$ Así que el algoritmo voraz falla exactamente cuando $N \ge 25$ y $r \in \{5, \ldots, 9\} \cup \{15, \ldots, 19\}.$

Cada clase de residuos módulo $25$ contiene $40$ valores de $N$ en $1, \ldots, 1000,$ así que estos $10$ residuos dan $400$ valores, de los cuales los $10$ valores menores que $25$ no cuentan (allí $q = 0$ ). El algoritmo voraz falla para $390$ valores y tiene éxito para $1000 - 390 = 610.$

In any optimal collection there are at most $9$ pennies (ten pennies could become a dime) and at most $4$ dimes (five dimes could become two quarters), so its dimes and pennies are worth at most $49$ cents. Hence an optimal collection uses either $q = \lfloor N/25 \rfloor$ quarters, like greedy, or $q - 1$ quarters. For an amount $v$ made only of dimes and pennies, the best count is $f(v) = \lfloor v/10 \rfloor + (v \bmod 10),$ which is what greedy does on the remainder.

Let $r = N \bmod 25.$ Greedy uses $q + f(r)$ coins, and the only rival uses $(q - 1) + f(r + 25)$ coins (possible when $q \ge 1$ ), so greedy fails exactly when $f(r + 25) \le f(r).$ Tabulating: for $r = 0, \ldots, 4,$ $f(r+25) = r + 7 \gt f(r) = r;$ for $r = 5, \ldots, 9,$ $f(r+25) = r - 2 \le r;$ for $r = 10, \ldots, 14,$ $f(r+25) = r - 2 \gt r - 9;$ for $r = 15, \ldots, 19,$ $f(r+25) = r - 11 \le r - 9;$ for $r = 20, \ldots, 24,$ $f(r+25) = r - 11 \gt r - 18.$ So greedy fails exactly when $N \ge 25$ and $r \in \{5, \ldots, 9\} \cup \{15, \ldots, 19\}.$

Each residue class mod $25$ contains $40$ values of $N$ in $1, \ldots, 1000,$ so these $10$ residues give $400$ values, of which the $10$ values less than $25$ do not count (there $q = 0$ ). Greedy fails for $390$ values and succeeds for $1000 - 390 = 610.$

2025 AIME II Problema 8

Solución:

El Problema 8 en otros años