Maths Olympiad Prep

Library / /32 of 48

Combinatorics Difficulty 6.4 National olympiad Prove it Greece

Let Σ={1,2,3,,n}\Sigma = \{1,2,3,\ldots,n\}. We want to make a partition of the set Σ\Sigma into three subsets AA, BB and Γ\Gamma mutually disjoint with ABΓ=ΣA \cup B \cup \Gamma = \Sigma and such that the sums of their elements SAS_A, SBS_B and SΓS_\Gamma, respectively, are equal. Examine if that is possible, in the following cases
(α) n=2014n = 2014; (β) n=2015n = 2015; (γ) n=2018n = 2018. (A. Fellouris)

Solution

(α) If that is possible, for n=2014n = 2014, then for the sum of the elements of Σ\Sigma we get SΣ=SA+SB+SΓ=3SAS_{\Sigma} = S_A + S_B + S_{\Gamma} = 3 \cdot S_A, that is, SΣS_{\Sigma} is a multiple of 33. But
S2014=10072015multiple of 3. S_{2014} = 1007 \cdot 2015 \neq \text{multiple of } 3.
Hence we cannot apply the wanted partition.

(β) For n=2015n = 2015 we have: S2015=100820150(mod3)S_{2015} = 1008 \cdot 2015 \equiv 0 \pmod{3}.
We observe that Σ\Sigma consists of the set M0={1,2,3,4,5}M_0 = \{1,2,3,4,5\} and from 335335 successive six-folds of the form:
Mk={6k,6k+1,6k+2,6k+3,6k+4,6k+5},k=1,2,,335. M_k = \{6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5\}, \quad k = 1, 2, \dots, 335.
We partition the set M0M_0 into three subsets with equal sums of their elements A0={1,4}A_0 = \{1,4\}, B0={2,3}B_0 = \{2,3\} and Γ0={5}\Gamma_0 = \{5\}. Taking in mind that
(6k+1)+(6k+4)=(6k+2)+(6k+3)=6k+(6k+5), for all k=1,2,,335, (6k+1)+(6k+4)=(6k+2)+(6k+3)=6k+(6k+5), \text{ for all } k=1,2,\dots,335,
The wanted partition is feasible by taking the sets:
A={1,4}{6k+1,6k+4:k=1,2,,335} A = \{1,4\} \cup \{6k+1,6k+4:k=1,2,\dots,335\}
B={2,3}{6k+2,6k+3:k=1,2,,335} B = \{2,3\} \cup \{6k+2,6k+3:k=1,2,\dots,335\}
Γ={5}{6k,6k+5:k=1,2,,335}. \Gamma = \{5\} \cup \{6k,6k+5:k=1,2,\dots,335\}.

(γ) For n=2018n = 2018 we have: S2018=100920190(mod3)S_{2018} = 1009 \cdot 2019 \equiv 0 \pmod{3}. As in (β) we observe that Σ\Sigma consists of M0={1,2,3,4,5,6,7,8}M_0 = \{1,2,3,4,5,6,7,8\} and from 335335 successive six-folds of the form:
Mk={6k+3,6k+4,6k+5,6k+6,6k+7,6k+8},k=1,2,,335. M_k = \{6k+3,6k+4,6k+5,6k+6,6k+7,6k+8\}, \quad k = 1,2,\dots,335.
First we partition M0M_0 into three subsets with equal sums of their elements A0={1,2,3,6}A_0 = \{1,2,3,6\}, B0={5,7}B_0 = \{5,7\} and Γ0={4,8}\Gamma_0 = \{4,8\}. Since for all k=0,1,,335k = 0,1,\dots,335 we have (6k+3)+(6k+8)=(6k+4)+(6k+7)=(6k+5)+(6k+6)(6k+3)+(6k+8)=(6k+4)+(6k+7)=(6k+5)+(6k+6), the wanted partition is possible by taking
A={1,2,3,6}{6k+3,6k+8:k=0,1,2,,335} A = \{1,2,3,6\} \cup \{6k+3,6k+8:k=0,1,2,\dots,335\}
B={5,7}{6k+4,6k+7:k=0,1,2,,335} B = \{5,7\} \cup \{6k+4,6k+7:k=0,1,2,\dots,335\}
Γ={4,8}{6k+5,6k+6:k=0,1,2,,335}. \Gamma = \{4,8\} \cup \{6k+5,6k+6:k=0,1,2,\dots,335\}.

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.