Question

Para enteros positivos $a,$ $b,$ y $c$ con $a \lt b \lt c,$ considera colecciones de estampillas postales de denominaciones $a,$ $b,$ y $c$ centavos que contienen al menos una estampilla de cada denominación. Si existe tal colección que contiene subcolecciones que valen cada número entero de centavos hasta $1000$ centavos, sea $f(a, b, c)$ el número mínimo de estampillas en tal colección. Halla la suma de los tres menores valores de $c$ tales que $f(a, b, c) = 97$ para alguna elección de $a$ y $b.$

For positive integers $a,$ $b,$ and $c$ with $a \lt b \lt c,$ consider collections of postage stamps in denominations $a,$ $b,$ and $c$ cents that contain at least one stamp of each denomination. If there exists such a collection that contains sub-collections worth every whole number of cents up to $1000$ cents, let $f(a, b, c)$ be the minimum number of stamps in such a collection. Find the sum of the three least values of $c$ such that $f(a, b, c) = 97$ for some choice of $a$ and $b.$

Respuesta

Solución:

Para formar $1$ centavo necesitamos $a = 1.$ Supón que la colección tiene $x$ de a uno, $y$ estampillas de $b,$ y $z$ de $c.$ El valor $b - 1$ debe formarse solo con las de a uno, así que $x \ge b - 1;$ el valor $c - 1$ debe formarse con las de a uno y las de $b,$ así que $x + yb \ge c - 1;$ y el total $x + yb + zc$ debe ser al menos $1000.$ Recíprocamente estas tres condiciones bastan: con $x \ge b - 1$ las de a uno y las de $b$ forman todo valor hasta $x + yb,$ y entonces las de $c$ lo extienden a todo valor hasta el total. Así que el óptimo toma $x = b - 1,$ luego el menor $y$ con $x + yb \ge c - 1,$ luego el menor $z$ que alcanza $1000.$

Fijado $c,$ el conteo $f(1, b, c)$ se maximiza en $b = c - 1$ (muchas de a uno, que cubren valor de la forma menos eficiente), donde la colección óptima es $c - 2$ de a uno, una estampilla de $c - 1,$ y $\left\lceil \frac{1003 - 2c}{c} \right\rceil$ estampillas de $c,$ para un total de $c - 3 + \left\lceil \frac{1003}{c} \right\rceil.$ Para $12 \le c \le 87$ este máximo es a lo sumo $96$ (es $93$ en $c = 12,$ decrece en el medio, y regresa a $96$ en $c = 87$ ), así que ningún $b$ da $97;$ una comprobación rápida de $c \le 10$ muestra que los conteos posibles también saltan $97$ ahí.

Para $c = 11,$ tomando $b = 7$ se obtienen $6$ de a uno, una de $7$ (alcanzando $13 \ge 10$ ), y $\left\lceil \frac{987}{11} \right\rceil = 90$ de a once: $f(1, 7, 11) = 6 + 1 + 90 = 97.$ Para $c = 88$ y $c = 89,$ tomando $b = 87$ se obtienen $86$ de a uno, una de $87$ (alcanzando $173$ ), y $\left\lceil \frac{827}{88} \right\rceil = \left\lceil \frac{827}{89} \right\rceil = 10$ estampillas de $c,$ para $86 + 1 + 10 = 97$ en ambos casos. Así que los tres menores valores de $c$ son $11, 88, 89,$ con suma $188.$

To form $1$ cent we need $a = 1.$ Suppose the collection has $x$ ones, $y$ stamps of $b,$ and $z$ of $c.$ The value $b - 1$ must be made from ones alone, so $x \ge b - 1;$ the value $c - 1$ must be made from ones and $b$ 's, so $x + yb \ge c - 1;$ and the total $x + yb + zc$ must be at least $1000.$ Conversely these three conditions suffice: with $x \ge b - 1$ the ones and $b$ 's make every value up to $x + yb,$ and then $c$ 's extend this to every value up to the total. So the optimum takes $x = b - 1,$ then the least $y$ with $x + yb \ge c - 1,$ then the least $z$ reaching $1000.$

For fixed $c,$ the count $f(1, b, c)$ is maximized at $b = c - 1$ (many ones, which cover value least efficiently), where the optimal collection is $c - 2$ ones, one stamp of $c - 1,$ and $\left\lceil \frac{1003 - 2c}{c} \right\rceil$ stamps of $c,$ totaling $c - 3 + \left\lceil \frac{1003}{c} \right\rceil.$ For $12 \le c \le 87$ this maximum is at most $96$ (it is $93$ at $c = 12,$ decreases in the middle, and returns to $96$ at $c = 87$ ), so no $b$ gives $97;$ a quick check of $c \le 10$ shows the possible counts skip $97$ there as well.

For $c = 11,$ taking $b = 7$ gives $6$ ones, one $7$ (reaching $13 \ge 10$ ), and $\left\lceil \frac{987}{11} \right\rceil = 90$ elevens: $f(1, 7, 11) = 6 + 1 + 90 = 97.$ For $c = 88$ and $c = 89,$ taking $b = 87$ gives $86$ ones, one $87$ (reaching $173$ ), and $\left\lceil \frac{827}{88} \right\rceil = \left\lceil \frac{827}{89} \right\rceil = 10$ stamps of $c,$ for $86 + 1 + 10 = 97$ in both cases. So the three least values of $c$ are $11, 88, 89,$ with sum $188.$

2022 AIME II Problema 14

Solución:

El Problema 14 en otros años