Maths Olympiad Prep

Library / /74 of 108

Combinatorics Difficulty 6.5 National Olympiad Prove it Mongolia

Denote by d(A)d(A) the sum of all the elements of AA (if A=A = \emptyset, d(A)=0d(A) = 0). Let S={1,2,,2013}S = \{1, 2, \dots, 2013\} and
Tr={TTS,d(T)r(mod7)}, T_r = \{T \mid T \subseteq S, d(T) \equiv r \pmod 7\},
for r=1,2,,6r = 1, 2, \dots, 6. Find the number of elements of TrT_r for each rr.

Solution

Consider f(x)=(1+x)(1+x2)(1+x2013)=nanxnf(x) = (1+x)(1+x^2)\dots(1+x^{2013}) = \sum_n a_n x^n. Then
Tr=k[x7k+r]f(x)=ka7k+r. |T_r| = \sum_k [x^{7k+r}] f(x) = \sum_k a_{7k+r}.
Let ϵ=e2πi7\epsilon = e^{\frac{2\pi i}{7}}, i.e. ϵ\epsilon is a 7th root of unity. We use the following well known facts.
1+ϵ+ϵ2++ϵ6=0,(1) 1 + \epsilon + \epsilon^2 + \dots + \epsilon^6 = 0, \quad (1)
k=16ϵkr=6, if 7r,k=16ϵkr=1, if 7r.(2) \sum_{k=1}^{6} \epsilon^{kr} = 6, \text{ if } 7 \mid r, \quad \sum_{k=1}^{6} \epsilon^{kr} = -1, \text{ if } 7 \nmid r. \quad (2)
Hence i=06f(ϵi)=i=06nanϵni=ni=06ϵni=7n7an=7T0\sum_{i=0}^{6} f(\epsilon^i) = \sum_{i=0}^{6} \sum_{n} a_n \epsilon^{ni} = \sum_{n} \sum_{i=0}^{6} \epsilon^{ni} = \sum_{7|n} 7a_n = 7|T_0|. Analogously,
Tr=17i=06ϵrif(ϵi)=17(22013+i=16ϵrif(ϵi)). |T_r| = \frac{1}{7} \sum_{i=0}^{6} \epsilon^{-ri} f(\epsilon^i) = \frac{1}{7} (2^{2013} + \sum_{i=1}^{6} \epsilon^{-ri} f(\epsilon^i)).
Let g(x)=x71=(xϵ)(xϵ2)(xϵ7)g(x) = x^7 - 1 = (x - \epsilon)(x - \epsilon^2)\dots(x - \epsilon^7). Then
g(1)=2=(1ϵ)(1ϵ2)(1ϵ7), g(-1) = -2 = (-1 - \epsilon)(-1 - \epsilon^2)\dots(-1 - \epsilon^7),
and
(1+ϵ)(1+ϵ2)(1+ϵ7)=2. (1 + \epsilon)(1 + \epsilon^2)\dots(1 + \epsilon^7) = 2.
Since ϵ7=1\epsilon^7 = 1 and 2013=7287+42013 = 7 \cdot 287 + 4,
f(ϵ)=(1+ϵ)(1+ϵ2)(1+ϵ2013)=[(1+ϵ)(1+ϵ2)(1+ϵ7)]287(1+ϵ)(1+ϵ2)(1+ϵ3)(1+ϵ4)==2287[(1+ϵ)(1+ϵ2)(1+ϵ4)](1+ϵ3)=2287[1+ϵ++ϵ7](1+ϵ3)=2287(1+ϵ3). f(\epsilon) = (1+\epsilon)(1+\epsilon^2)\dots(1+\epsilon^{2013}) = [(1+\epsilon)(1+\epsilon^2)\dots(1+\epsilon^7)]^{287}(1+\epsilon)(1+\epsilon^2)(1+\epsilon^3)(1+\epsilon^4) = \\ = 2^{287}[(1+\epsilon)(1+\epsilon^2)(1+\epsilon^4)](1+\epsilon^3) = 2^{287}[1+\epsilon+\dots+\epsilon^7](1+\epsilon^3) = 2^{287}(1+\epsilon^3).
Thus f(ϵi)=2287(1+ϵ3i)f(\epsilon^i) = 2^{287}(1 + \epsilon^{3i}), for 1i61 \le i \le 6.
Tr=17[22013+2287i=16(ϵri+ϵ(3r)i)]. |T_r| = \frac{1}{7} [2^{2013} + 2^{287} \cdot \sum_{i=1}^{6} (\epsilon^{-ri} + \epsilon^{(3-r)i})].
From (1) and (2)
i=16(ϵri+ϵ(3r)i)={61=5,r=0,311=2,r=1,2,4,5,6 \sum_{i=1}^{6} (\epsilon^{-ri} + \epsilon^{(3-r)i}) = \begin{cases} 6-1=5, & r=0,3 \\ -1-1= -2, & r=1,2,4,5,6 \end{cases}
Hence
Tr={22013+522877,r=0,32201322887,r=1,2,4,5,6 |T_r| = \begin{cases} \frac{2^{2013} + 5 \cdot 2^{287}}{7}, & r = 0, 3 \\ \frac{2^{2013} - 2^{288}}{7}, & r = 1, 2, 4, 5, 6 \end{cases}

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 reproduced verbatim; metadata (topic, difficulty) added by this project.