2018 AIME I 第 12 题

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

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

12.

对集合 U={1,2,3,…,18}U = \{1, 2, 3, \ldots, 18\} 的每个子集 TT,令 s(T)s(T) 为 TT 中元素之和,并规定 s(∅)s(\emptyset) 为 00。若从 UU 的所有子集中随机选取 TT,则 s(T)s(T) 能被 33 整除的概率为 mn\frac{m}{n},其中 mm 与 nn 是互质正整数。求 mm。

For each subset TT of U={1,2,3,…,18},U = \{1, 2, 3, \ldots, 18\}, let s(T)s(T) be the sum of the elements of T,T, with s(∅)s(\emptyset) defined to be 0.0. If TT is chosen at random among all subsets of U,U, the probability that s(T)s(T) is divisible by 33 is mn,\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m.m.

答案:683
知识点:子集模运算组合范德蒙德卷积
难度评级:3060
小提示:

模 33 的每个余数类在 UU 中都恰有六个元素,并且只有所选的 ≡1\equiv 1 和 ≡2\equiv 2 的元素个数重要

Each residue class modulo 33 contains exactly six elements of U,U, and only the numbers of chosen elements ≡1\equiv 1 and ≡2\equiv 2 matter

大提示:

若选了 aa 个 ≡1\equiv 1 的元素与 bb 个 ≡2\equiv 2 的元素,需要 a≡b(mod3)a \equiv b \pmod 3;用范德蒙德恒等式计算 ∑(6a)(6b)\sum \binom{6}{a}\binom{6}{b}

With aa chosen elements ≡1\equiv 1 and bb elements ≡2,\equiv 2, you need a≡b(mod3);a \equiv b \pmod 3; evaluate ∑(6a)(6b)\sum \binom{6}{a}\binom{6}{b} using Vandermonde’s identity

解答:

集合 UU 在模 33 的每个余数类中各有六个元素。若 TT 包含 aa 个 ≡1\equiv 1 的元素和 bb 个 ≡2(mod3)\equiv 2 \pmod 3 的元素,则 s(T)≡a+2b≡a−b(mod3)s(T) \equiv a + 2b \equiv a - b \pmod 3,所以 s(T)s(T) 能被 33 整除当且仅当 a≡b(mod3)a \equiv b \pmod 3;六个 33 的倍数可自由选择,对有利数与总数都贡献因子 262^6。

由范德蒙德恒等式,选择这些 aa 与 bb 时,满足 a−b=0a - b = 0 的选法数为 ∑a(6a)2=(126)=924\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924;满足 a−b=±3a - b = \pm 3 的选法数为 2∑a(6a)(6a−3)=2(129)=4402\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440;满足 a−b=±6a - b = \pm 6 的选法数为 22。有利选法为 924+440+2=1366924 + 440 + 2 = 1366,总数为 2122^{12}。

概率为 13664096=6832048\frac{1366}{4096} = \frac{683}{2048},由于 683683 是奇数,已经最简。因此 m=683m = 683。

The set UU contains six elements in each residue class modulo 3.3. If TT contains aa elements ≡1\equiv 1 and bb elements ≡2(mod3),\equiv 2 \pmod 3, then s(T)≡a+2b≡a−b(mod3),s(T) \equiv a + 2b \equiv a - b \pmod 3, so s(T)s(T) is divisible by 33 exactly when a≡b(mod3);a \equiv b \pmod 3; the six multiples of 33 may be included freely, contributing a factor 262^6 to both the favorable and total counts.

By Vandermonde’s identity, the number of ways to choose the aas and bbs with a−b=0a - b = 0 is ∑a(6a)2=(126)=924;\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924; with a−b=±3a - b = \pm 3 it is 2∑a(6a)(6a−3)=2(129)=440;2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440; and with a−b=±6a - b = \pm 6 it is 2.2. The favorable choices number 924+440+2=1366924 + 440 + 2 = 1366 out of 212.2^{12}.

The probability is 13664096=6832048,\frac{1366}{4096} = \frac{683}{2048}, which is in lowest terms since 683683 is odd. Thus m=683.m = 683.

第 11 题#11
完整试卷

其他年份的第 12 题