Question

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

答案

Solution:

The set $U$ contains six elements in each residue class modulo $3.$ If $T$ contains $a$ elements $\equiv 1$ and $b$ elements $\equiv 2 \pmod 3,$ then $s(T) \equiv a + 2b \equiv a - b \pmod 3,$ so $3 \mid s(T)$ exactly when $a \equiv b \pmod 3;$ the six multiples of $3$ may be included freely, contributing a factor $2^6$ to both the favorable and total counts.

By Vandermonde's identity, the number of ways to choose the $a$ s and $b$ s with $a - b = 0$ is $\sum_a \binom{6}{a}^2 = \binom{12}{6} = 924;$ with $a - b = \pm 3$ it is $2\sum_a \binom{6}{a}\binom{6}{a - 3} = 2\binom{12}{9} = 440;$ and with $a - b = \pm 6$ it is $2.$ The favorable choices number $924 + 440 + 2 = 1366$ out of $2^{12}.$

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

2018 AIME I Problem 12

Solution:

Problem 12 in Other Years