Maths Olympiad Prep

Library / /22 of 54

Combinatorics Difficulty 6.0 AIME, harder Prove it China

Let T={1,2,3,4,5,6,7,8}T = \{1, 2, 3, 4, 5, 6, 7, 8\}. Find the number of all nonempty subsets AA of TT such that 3S(A)3|S(A) and 5S(A)5 \nmid S(A), where S(A)S(A) is the sum of all elements of AA.

Solution

Define S()=0S(\emptyset) = 0. Let T0={3,6}T_0 = \{3, 6\}, T1={1,4,7}T_1 = \{1, 4, 7\}, T2={2,5,8}T_2 = \{2, 5, 8\}. For ATA \subseteq T, let A0=AT0A_0 = A \cap T_0, A1=AT1A_1 = A \cap T_1, A2=AT2A_2 = A \cap T_2, then

S(A)=S(A0)+S(A1)+S(A2)A1A2(mod3), S(A) = S(A_0) + S(A_1) + S(A_2) \equiv |A_1| - |A_2| \pmod{3},

So 3S(A)3|S(A) if and only if A1A2(mod3)|A_1| \equiv |A_2| \pmod{3}. It follows that
(A1,A2)=(0,0),(0,3),(3,0),(3,3),(1,1),(2,2). (|A_1|, |A_2|) = (0, 0), (0, 3), (3, 0), (3, 3), (1, 1), (2, 2).

The number of nonempty subsets AA so that 3S(A)3|S(A) is
22(30)(30)+(30)(33)+(33)(30)+(33)(33)+(31)(31)+(32)(32)1=87. 2^2 \binom{3}{0} \binom{3}{0} + \binom{3}{0} \binom{3}{3} + \binom{3}{3} \binom{3}{0} + \binom{3}{3} \binom{3}{3} \\ + \binom{3}{1} \binom{3}{1} + \binom{3}{2} \binom{3}{2} - 1 = 87.

If 3S(A)3|S(A) and 5S(A)5|S(A), then 15S(A)15|S(A). Since S(T)=36S(T) = 36, so the value S(A)S(A) is 15 or 30 (if 3S(A)3|S(A) and 5S(A)5|S(A)).

Furthermore,
15=8+7=8+6+1=8+5+2=8+4+3=8+4+2+1=7+6+2=7+5+3=7+5+2+1=7+4+3+1=6+5+4=6+5+3+1=6+4+3+2=5+4+3+2+1, \begin{aligned} 15 &= 8+7 = 8+6+1 = 8+5+2 = 8+4+3 \\ &= 8+4+2+1 = 7+6+2 = 7+5+3 \\ &= 7+5+2+1 = 7+4+3+1 = 6+5+4 \\ &= 6+5+3+1 = 6+4+3+2 \\ &= 5+4+3+2+1, \end{aligned}
3630=6=5+1=4+2=3+2+1. 36 - 30 = 6 = 5 + 1 = 4 + 2 = 3 + 2 + 1.
So the number of AA such that 3S(A)3|S(A), 5S(A)5|S(A), and AA \neq \emptyset is 17.

The answer is 8717=7087 - 17 = 70.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.