Logo para LIVE por Po-Shen Loh

LIVE

2022 AIME II Problema 14

Intenta el Problema 14 del 2022 AIME II a continuación y luego compara tu respuesta con la solución preparada profesionalmente de LIVE by Po-Shen Loh. También puedes intentar el examen cronometrado completo, ver todas las soluciones del 2022 AIME II, o revisar la clave de respuestas.

Todos los problemas se usan con el permiso legal oficial de la Mathematical Association of America (MAA).

14.

Para enteros positivos a,a, b,b, y cc con a<b<c,a \lt b \lt c, considera colecciones de estampillas postales de denominaciones a,a, b,b, y cc 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 10001000 centavos, sea f(a,b,c)f(a, b, c) el número mínimo de estampillas en tal colección. Halla la suma de los tres menores valores de cc tales que f(a,b,c)=97f(a, b, c) = 97 para alguna elección de aa y b.b.
For positive integers a,a, b,b, and cc with a<b<c,a \lt b \lt c, consider collections of postage stamps in denominations a,a, b,b, and cc 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 10001000 cents, let f(a,b,c)f(a, b, c) be the minimum number of stamps in such a collection. Find the sum of the three least values of cc such that f(a,b,c)=97f(a, b, c) = 97 for some choice of aa and b.b.
Respuesta: 188
Conceptos:optimizaciónfunciones piso y techoanálisis por casos
Nivel de dificultad: 3500
Pista pequeña:
Formar 11 centavo obliga a a=1.a = 1. Una colección funciona exactamente cuando las de a uno alcanzan b−1,b - 1, las de a uno y las de bb juntas alcanzan c−1,c - 1, y el valor total es al menos 1000.1000.
Making 11 cent forces a=1.a = 1. A collection works exactly when the ones reach b−1,b - 1, the ones and bb’s together reach c−1,c - 1, and the total value is at least 1000.1000.
Pista grande:
Para cc fijo el número de estampillas es máximo en b=c−1,b = c - 1, donde vale c−3+⌈1003c⌉;c - 3 + \lceil \frac{1003}{c} \rceil; para 12≤c≤8712 \le c \le 87 esto nunca llega a 9797
For fixed cc the stamp count is largest at b=c−1,b = c - 1, where it equals c−3+⌈1003c⌉;c - 3 + \lceil \frac{1003}{c} \rceil; for 12≤c≤8712 \le c \le 87 this never reaches 9797
Solución:
Para formar 11 centavo necesitamos a=1.a = 1. Supongamos que la colección tiene xx estampillas de uno, yy estampillas de b,b, y zz estampillas de c.c. El valor b−1b - 1 debe formarse solo con estampillas de uno, así que x≥b−1;x \ge b - 1; el valor c−1c - 1 debe formarse con estampillas de uno y de bb, así que x+yb≥c−1;x + yb \ge c - 1; y el total x+yb+zcx + yb + zc debe ser al menos 1000.1000. Recíprocamente, estas tres condiciones bastan: con x≥b−1x \ge b - 1, las estampillas de uno y de bb forman todos los valores hasta x+yb,x + yb, y las estampillas de cc extienden el intervalo hasta el valor total. Por tanto, el óptimo toma x=b−1,x = b - 1, luego el menor yy con x+yb≥c−1,x + yb \ge c - 1, y después el menor zz que alcanza 1000.1000.
Para cc fijo, ningún bb puede requerir más estampillas que b=c−1.b=c-1. En efecto, para cualquier 2≤b<c,2\le b\lt c, tomemos b−1b-1 estampillas de uno y c−bc-b estampillas de b.b. Estas c−1c-1 estampillas de denominación menor tienen valor total b−1+b(c−b)≥2c−3, b-1+b(c-b)\ge 2c-3, porque la diferencia es (b−2)(c−b−1)≥0.(b-2)(c-b-1)\ge0. Al agregar ⌈1003c⌉−2\left\lceil\frac{1003}{c}\right\rceil-2 estampillas de cc, obtenemos una colección válida de a lo sumo c−3+⌈1003c⌉c-3+\left\lceil\frac{1003}{c}\right\rceil estampillas. La igualdad se alcanza cuando b=c−1:b=c-1: las c−2c-2 estampillas obligatorias de uno y una estampilla de c−1c-1 tienen valor 2c−3,2c-3, y estampillas de valor máximo cc no pueden alcanzar 10001000 con menos de c−3+⌈1003c⌉ c-3+\left\lceil\frac{1003}{c}\right\rceil estampillas en total.
Para 12≤c≤87,12\le c\le87, las cotas en los extremos c(99−c)≥1003c(99-c)\ge1003 dan ⌈1003c⌉≤99−c,\left\lceil\frac{1003}{c}\right\rceil\le99-c, así que este máximo es a lo sumo 9696 y ningún bb da 97.97. Para c≤10,c\le10, cualesquiera 9797 estampillas tienen valor total a lo sumo 97c≤970,97c\le970, así que no pueden cubrir todos los valores hasta 1000.1000.
Para c=11,c = 11, tomar b=7b = 7 da 66 estampillas de uno, una de 77 (alcanzando 13≥1013 \ge 10), y ⌈98711⌉=90\left\lceil \frac{987}{11} \right\rceil = 90 estampillas de once: f(1,7,11)=6+1+90=97.f(1, 7, 11) = 6 + 1 + 90 = 97. Para c=88c = 88 y c=89,c = 89, tomar b=87b = 87 da 8686 estampillas de uno, una de 8787 (alcanzando 173173), y ⌈82788⌉=⌈82789⌉=10\left\lceil \frac{827}{88} \right\rceil = \left\lceil \frac{827}{89} \right\rceil = 10 estampillas de c,c, para un total de 86+1+10=9786 + 1 + 10 = 97 en ambos casos. Así, los tres menores valores de cc son 11,88,89,11, 88, 89, cuya suma es 188.188.
To form 11 cent we need a=1.a = 1. Suppose the collection has xx ones, yy stamps of b,b, and zz of c.c. The value b−1b - 1 must be made from ones alone, so x≥b−1;x \ge b - 1; the value c−1c - 1 must be made from ones and bb’s, so x+yb≥c−1;x + yb \ge c - 1; and the total x+yb+zcx + yb + zc must be at least 1000.1000. Conversely these three conditions suffice: with x≥b−1x \ge b - 1 the ones and bb’s make every value up to x+yb,x + yb, and then cc’s extend this to every value up to the total. So the optimum takes x=b−1,x = b - 1, then the least yy with x+yb≥c−1,x + yb \ge c - 1, then the least zz reaching 1000.1000.
For fixed c,c, no bb can require more stamps than b=c−1.b=c-1. Indeed, for any 2≤b<c,2\le b\lt c, take b−1b-1 ones and c−bc-b stamps of b.b. These c−1c-1 lower-denomination stamps have total value b−1+b(c−b)≥2c−3, b-1+b(c-b)\ge 2c-3, because the difference is (b−2)(c−b−1)≥0.(b-2)(c-b-1)\ge0. Adding ⌈1003c⌉−2\left\lceil\frac{1003}{c}\right\rceil-2 stamps of cc therefore gives a working collection of at most c−3+⌈1003c⌉c-3+\left\lceil\frac{1003}{c}\right\rceil stamps. Equality is attained when b=c−1:b=c-1: the mandatory c−2c-2 ones and one c−1c-1 stamp have value 2c−3,2c-3, and stamps of value at most cc cannot reach 10001000 with fewer than c−3+⌈1003c⌉ c-3+\left\lceil\frac{1003}{c}\right\rceil stamps in total.
For 12≤c≤87,12\le c\le87, the endpoint bounds c(99−c)≥1003c(99-c)\ge1003 give ⌈1003c⌉≤99−c,\left\lceil\frac{1003}{c}\right\rceil\le99-c, so this maximum is at most 9696 and no bb gives 97.97. For c≤10,c\le10, any 9797 stamps have total value at most 97c≤970,97c\le970, so they cannot cover every value through 1000.1000.
For c=11,c = 11, taking b=7b = 7 gives 66 ones, one 77 (reaching 13≥1013 \ge 10), and ⌈98711⌉=90\left\lceil \frac{987}{11} \right\rceil = 90 elevens: f(1,7,11)=6+1+90=97.f(1, 7, 11) = 6 + 1 + 90 = 97. For c=88c = 88 and c=89,c = 89, taking b=87b = 87 gives 8686 ones, one 8787 (reaching 173173), and ⌈82788⌉=⌈82789⌉=10\left\lceil \frac{827}{88} \right\rceil = \left\lceil \frac{827}{89} \right\rceil = 10 stamps of c,c, for 86+1+10=9786 + 1 + 10 = 97 in both cases. So the three least values of cc are 11,88,89,11, 88, 89, with sum 188.188.
Problema 13#13
Examen completo
Problema 15#15

El Problema 14 en otros años

1983 AIME · 1984 AIME · 1985 AIME · 1986 AIME · 1987 AIME · 1988 AIME · 1989 AIME · 1990 AIME · 1991 AIME · 1992 AIME · 1993 AIME · 1994 AIME · 1995 AIME · 1996 AIME · 1997 AIME · 1998 AIME · 1999 AIME · 2000 AIME I · 2000 AIME II · 2001 AIME I · 2001 AIME II · 2002 AIME I · 2002 AIME II · 2003 AIME I · 2003 AIME II · 2004 AIME I · 2004 AIME II · 2005 AIME I · 2005 AIME II · 2006 AIME I · 2006 AIME II · 2007 AIME I · 2007 AIME II · 2008 AIME I · 2008 AIME II · 2009 AIME I · 2009 AIME II · 2010 AIME I · 2010 AIME II · 2011 AIME I · 2011 AIME II · 2012 AIME I · 2012 AIME II · 2013 AIME I · 2013 AIME II · 2014 AIME I · 2014 AIME II · 2015 AIME I · 2015 AIME II · 2016 AIME I · 2016 AIME II · 2017 AIME I · 2017 AIME II · 2018 AIME I · 2018 AIME II · 2019 AIME I · 2019 AIME II · 2020 AIME I · 2020 AIME II · 2021 AIME I · 2021 AIME II · 2022 AIME I · 2023 AIME I · 2023 AIME II · 2024 AIME I · 2024 AIME II · 2025 AIME I · 2025 AIME II · 2026 AIME I · 2026 AIME II