2019 AIME II Problema 14

A continuación está la solución preparada profesionalmente para el Problema 14 del 2019 AIME II, de LIVE by Po-Shen Loh. También puedes intentar el examen cronometrado completo, ver todas las soluciones del 2019 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).

Conceptos:Teorema de Chicken McNugget (Frobenius)aritmética modularanálisis por casos

Nivel de dificultad: 3060

14.

Halle la suma de todos los enteros positivos nn tales que, dada una cantidad ilimitada de sellos de denominaciones 5,5, n,n, y n+1n + 1 centavos, 9191 centavos es el mayor franqueo que no se puede formar.

Find the sum of all positive integers nn such that, given an unlimited supply of stamps of denominations 5,5, n,n, and n+1n + 1 cents, 9191 cents is the greatest postage that cannot be formed.

Solución:

Usar kk sellos de las denominaciones nn y n+1n + 1 produce exactamente las cantidades kn+ckn + c para 0ck,0 \le c \le k, y agregar sellos de 55 centavos cubre entonces todo lo que está por encima en la misma clase residual módulo 5.5. Así que en cada clase rr toda cantidad de al menos m(r)m(r) es formable y ninguna menor lo es, donde m(r)m(r) es el menor valor de kn+ckn + c (0ck)(0 \le c \le k) congruente con rr módulo 5.5. La mayor cantidad no formable es maxrm(r)5,\max_r m(r) - 5, así que necesitamos maxrm(r)=96:\max_r m(r) = 96: la clase de 9696 (que es 11 módulo 55) debe cubrirse por primera vez exactamente en 96,96, y toda otra clase no más tarde.

Distinga casos según nmod5,n \bmod 5, notando que kn+ckn+c.kn + c \equiv kn + c. Si n4:n \equiv 4: la clase 11 necesita 4k+c14k + c \equiv 1 con ck,c \le k, posible por primera vez en k=4,k = 4, c=0,c = 0, así que 4n=964n = 96 y n=24;n = 24; las demás clases se cubren en 24,24, 48,48, 72,72, todas menores que 96,96, así que n=24n = 24 funciona. Si n2:n \equiv 2: la clase 11 se cubre por primera vez en k=2,k = 2, c=2,c = 2, así que 2n+2=962n + 2 = 96 y n=47;n = 47; las demás clases se cubren en 47,47, 48,48, 9496,94 \le 96, así que n=47n = 47 funciona.

Si n3:n \equiv 3: la clase 11 primero en 2n=96,2n = 96, así que n=48,n = 48, pero entonces la clase 22 se cubre por primera vez en 2n+1=97>962n + 1 = 97 \gt 96, falla. Si n1:n \equiv 1: la clase 11 primero en n=96,n = 96, pero entonces la clase 33 se cubre por primera vez en 2n+1=1932n + 1 = 193, falla. Si n0:n \equiv 0: la clase 11 primero en n+1=96,n + 1 = 96, así que n=95,n = 95, pero la clase 44 necesita c=4,c = 4, k4,k \ge 4, dando 4n+4>964n + 4 \gt 96, falla. La respuesta es 24+47=71.24 + 47 = 71.

Using kk stamps of the denominations nn and n+1n + 1 produces exactly the amounts kn+ckn + c for 0ck,0 \le c \le k, and adding 55-cent stamps then covers everything above in the same residue class mod 5.5. So in each class rr every amount at least m(r)m(r) is formable and nothing smaller is, where m(r)m(r) is the least value of kn+ckn + c (0ck)(0 \le c \le k) congruent to rr mod 5.5. The greatest non-formable amount is maxrm(r)5,\max_r m(r) - 5, so we need maxrm(r)=96:\max_r m(r) = 96: the class of 9696 (which is 11 mod 55) must be covered first exactly at 96,96, and every other class no later.

Case on nmod5,n \bmod 5, noting kn+ckn+c.kn + c \equiv kn + c. If n4:n \equiv 4: class 11 needs 4k+c14k + c \equiv 1 with ck,c \le k, first possible at k=4,k = 4, c=0,c = 0, so 4n=964n = 96 and n=24;n = 24; the other classes are covered at 24,24, 48,48, 72,72, all less than 96,96, so n=24n = 24 works. If n2:n \equiv 2: class 11 is first covered at k=2,k = 2, c=2,c = 2, so 2n+2=962n + 2 = 96 and n=47;n = 47; the other classes are covered at 47,47, 48,48, 9496,94 \le 96, so n=47n = 47 works.

If n3:n \equiv 3: class 11 first at 2n=96,2n = 96, so n=48,n = 48, but then class 22 is first covered at 2n+1=97>962n + 1 = 97 \gt 96 — fails. If n1:n \equiv 1: class 11 first at n=96,n = 96, but then class 33 is first covered at 2n+1=1932n + 1 = 193 — fails. If n0:n \equiv 0: class 11 first at n+1=96,n + 1 = 96, so n=95,n = 95, but class 44 needs c=4,c = 4, k4,k \ge 4, giving 4n+4>964n + 4 \gt 96 — fails. The answer is 24+47=71.24 + 47 = 71.

← Problema 13#13Examen completoProblema 15#15 →

El Problema 14 en otros años