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