2019 AIME II Problem 14

Attempt Problem 14 of the 2019 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2019 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

14.

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.

Answer: 71
Concepts:Chicken McNugget Theoremmodular arithmeticcasework
Difficulty rating: 3060
Solution:

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.

← Problem 13#13
Full Exam

Problem 14 in Other Years