Problem:
For each subset T of U={1,2,3,…,18}, let s(T) be the sum of the elements of T, with s(∅) 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 nm, where m and n are relatively prime positive integers. Find m.
Solution:
Let A={1,4,7,10,13,16},B={2,5,8,11,14,17}, and C={3,6,9,12,15,18}. For T⊆U, let a=∣T∩A∣,b=∣T∩B∣, and c=∣T∩C∣. Then s(T) is divisible by 3 if and only if ∣a−b∣=0,3, or 6. Because elements of T∩C do not influence whether 3 divides s(T), it suffices to calculate the conditional probability that s(T) is divisible by 3 given that T∩C=∅.
The number of subsets with a−b=0 is
k=0∑6(6k)2=k=0∑6(6k)(66−k)=(126)=924
The number of subsets with a−b=3 is
k=0∑3(6k+3)(6k)=k=0∑3(63−k)(6k)=(123)=220
and the number with b−a=3 is the same. There is one subset with a−b=6 and one with b−a=6. Hence the number of sets T for which s(T) is divisible by 3 and T∩C=∅ is 924+2⋅220+2=1366. The required probability is 2121366=211683. The requested numerator is 683.
OR
Defining A and B as above, associate with each T⊆A∪B the set T∗= (T∩A)∪(B\T). Then T has a+b elements if and only if T∗ has a+(6−b)=6+(a−b) elements, so a−b is a multiple of 3 if and only if T∗ contains 0,3,6,9, or 12 elements. Therefore the number of sets T∗ is
(120)+(123)+(126)+(129)+(1212)=1366
OR
Consider the function
F(X)=k=1∏18(1+Xk)=T⊆U∑Xs(T)
Note that if ω is a cube root of unity not equal to 1, then 1k+ωk+ω2k equals 3 when k is divisible by 3, and it equals 0 otherwise. Then the number N of sets T with s(T)≡0(mod3) is
N=3F(1)+F(ω)+F(ω2)
Now F(1)=218, while
F(ω)=F(ω2)=(2(1+ω)(1+ω2))6=26.
Hence
N=3218+64+64=3211+1⋅27
meaning p=3211+1=683.
The problems on this page are the property of the MAA's American Mathematics Competitions