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

Respuesta: 188

Conceptos:optimización funciones piso y techo análisis por casos

Nivel de dificultad: 3500

Solución:

Para formar $1$ centavo necesitamos $a = 1.$ Supongamos que la colección tiene $x$ estampillas de uno, $y$ estampillas de $b,$ y $z$ estampillas de $c.$ El valor $b - 1$ debe formarse solo con estampillas de uno, así que $x \ge b - 1;$ el valor $c - 1$ debe formarse con estampillas de uno y 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 estampillas de uno y de $b$ forman todos los valores hasta $x + yb,$ y las estampillas de $c$ extienden el intervalo hasta el valor total. Por tanto, el óptimo toma $x = b - 1,$ luego el menor $y$ con $x + yb \ge c - 1,$ y después el menor $z$ que alcanza $1000.$

Para $c$ fijo, ningún $b$ puede requerir más estampillas que $b=c-1.$ En efecto, para cualquier $2\le b\lt c,$ tomemos $b-1$ estampillas de uno y $c-b$ estampillas de $b.$ Estas $c-1$ estampillas de denominación menor tienen valor total $b-1+b(c-b)\ge 2c-3,$ porque la diferencia es $(b-2)(c-b-1)\ge0.$ Al agregar $\left\lceil\frac{1003}{c}\right\rceil-2$ estampillas de $c$ , obtenemos una colección válida de a lo sumo $c-3+\left\lceil\frac{1003}{c}\right\rceil$ estampillas. La igualdad se alcanza cuando $b=c-1:$ las $c-2$ estampillas obligatorias de uno y una estampilla de $c-1$ tienen valor $2c-3,$ y estampillas de valor máximo $c$ no pueden alcanzar $1000$ con menos de $c-3+\left\lceil\frac{1003}{c}\right\rceil$ estampillas en total.

Para $12\le c\le87,$ las cotas en los extremos $c(99-c)\ge1003$ dan $\left\lceil\frac{1003}{c}\right\rceil\le99-c,$ así que este máximo es a lo sumo $96$ y ningún $b$ da $97.$ Para $c\le10,$ cualesquiera $97$ estampillas tienen valor total a lo sumo $97c\le970,$ así que no pueden cubrir todos los valores hasta $1000.$

Para $c = 11,$ tomar $b = 7$ da $6$ estampillas de uno, una de $7$ (alcanzando $13 \ge 10$ ), y $\left\lceil \frac{987}{11} \right\rceil = 90$ estampillas de once: $f(1, 7, 11) = 6 + 1 + 90 = 97.$ Para $c = 88$ y $c = 89,$ tomar $b = 87$ da $86$ estampillas de 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 un total de $86 + 1 + 10 = 97$ en ambos casos. Así, los tres menores valores de $c$ son $11, 88, 89,$ cuya suma es $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,$ no $b$ can require more stamps than $b=c-1.$ Indeed, for any $2\le b\lt c,$ take $b-1$ ones and $c-b$ stamps of $b.$ These $c-1$ lower-denomination stamps have total value $b-1+b(c-b)\ge 2c-3,$ because the difference is $(b-2)(c-b-1)\ge0.$ Adding $\left\lceil\frac{1003}{c}\right\rceil-2$ stamps of $c$ therefore gives a working collection of at most $c-3+\left\lceil\frac{1003}{c}\right\rceil$ stamps. Equality is attained when $b=c-1:$ the mandatory $c-2$ ones and one $c-1$ stamp have value $2c-3,$ and stamps of value at most $c$ cannot reach $1000$ with fewer than $c-3+\left\lceil\frac{1003}{c}\right\rceil$ stamps in total.

For $12\le c\le87,$ the endpoint bounds $c(99-c)\ge1003$ give $\left\lceil\frac{1003}{c}\right\rceil\le99-c,$ so this maximum is at most $96$ and no $b$ gives $97.$ For $c\le10,$ any $97$ stamps have total value at most $97c\le970,$ so they cannot cover every value through $1000.$

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

Respuesta: 188

Nivel de dificultad: 3500

Solución:

El Problema 14 en otros años