2019 AIME II 第 14 题

先试着解答 2019 AIME II 第 14 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2019 AIME II 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

14.

求所有正整数 nn 的和,使得在有无限多张面值为 55nnn+1n + 1 分的邮票时,9191 分是无法拼出的最大邮资。

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.

答案:71
知识点:麦乐鸡定理模运算分类讨论
难度评级:3060
解答:

使用 kk 张面值为 nnn+1n + 1 的邮票,恰能得到 kn+ckn + c,其中 0ck0 \le c \le k,再加 55 分邮票,就覆盖同一模 55 余数类中其后的所有金额。因此在每个余数类 rr 中,所有不小于 m(r)m(r) 的金额都可拼出,而更小的不可拼出,其中 m(r)m(r) 是满足 kn+ckn + c (0ck)(0 \le c \le k) 同余于 rr55 的最小值。最大不可拼金额为 maxrm(r)5\max_r m(r) - 5,所以需要 maxrm(r)=96\max_r m(r) = 969696 所在的余数类(即模 5511)必须恰好先在 9696 被覆盖,而其他余数类不晚于它。

nmod5n \bmod 5, 分类,注意 kn+ckn+ckn + c \equiv kn + c。若 n4n \equiv 4:余数类 11 需要 4k+c14k + c \equiv 1ckc \le k,最早在 k=4k = 4c=0c = 0 时可行,所以 4n=964n = 96n=24n = 24;其他余数类在 242448487272, 就被覆盖,都小于 9696,因此 n=24n = 24 可行。若 n2n \equiv 2:余数类 11 最早在 k=2k = 2c=2c = 2 时被覆盖,所以 2n+2=962n + 2 = 96n=47n = 47;其他余数类在 47474848949694 \le 96 时被覆盖,所以 n=47n = 47 可行。

n3n \equiv 3:余数类 11 最早在 2n=962n = 96 时被覆盖,所以 n=48n = 48,但余数类 22 最早在 2n+1=97>962n + 1 = 97 \gt 96 时才被覆盖,失败。若 n1n \equiv 1:余数类 11 最早在 n=96n = 96 时被覆盖,但余数类 33 最早在 2n+1=1932n + 1 = 193 时才被覆盖,失败。若 n0n \equiv 0:余数类 11 最早在 n+1=96n + 1 = 96 时被覆盖,所以 n=95n = 95,但余数类 44 需要 c=4c = 4k4k \ge 4,得到 4n+4>964n + 4 \gt 96,失败。答案为 24+47=7124 + 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.

← 第 13 题#13
完整试卷

其他年份的第 14 题