Maths Olympiad Prep

Library / /230 of 520

Combinatorics Difficulty 6.4 National olympiad Prove it

22. (PHI 1) IMO1 { }^{\text {IMO1 }} Prove that the set {1,2,,1989}\{1,2, \ldots, 1989\} can be expressed as the disjoint union of 17 subsets A1,A2,,A17A_{1}, A_{2}, \ldots, A_{17} such that: (i) each AiA_{i} contains the same number of elements; (ii) the sum of all elements of each AiA_{i} is the same for i=1,2,,17i=1,2, \ldots, 17.

Solution

22. The statement remains valid if 17 is replaced by any divisor k k of 1989=321317 1989 = 3^2 \cdot 13 \cdot 17 , 1<k<1989 1 < k < 1989 , so let k k be one such divisor. The set {1,2,,1989} \{1, 2, \ldots, 1989\} can be partitioned as {1,2,,3k}j=1L{(2j+1)k+1,(2j+1)k+2,,(2j+1)k+2k}=XY1YL \{1, 2, \ldots, 3k\} \cup \bigcup_{j=1}^{L} \{(2j+1)k+1, (2j+1)k+2, \ldots, (2j+1)k+2k\} = X \cup Y_1 \cup \cdots \cup Y_L , where L=(19893k)/2k L = (1989 - 3k) / 2k . The required statement will be an obvious consequence of the following two claims.

Claim 1. The set X={1,2,,3k} X = \{1, 2, \ldots, 3k\} can be partitioned into k k disjoint subsets, each having 3 elements and the same sum.

Proof. Since k k is odd, let t=(k1)/2 t = (k-1) / 2 and X={1,2,,6t+3} X = \{1, 2, \ldots, 6t+3\} . For l=1,2,,t l = 1, 2, \ldots, t , define
X2l1={l,3t+1+l,6t+52l}X2l={t+1+l,2t+1+l,6t+42l}X2t+1=Xk={t+1,4t+2,4t+3} \begin{aligned} X_{2l-1} & = \{l, 3t+1+l, 6t+5-2l\} \\ X_{2l} & = \{t+1+l, 2t+1+l, 6t+4-2l\} \\ X_{2t+1} & = X_k = \{t+1, 4t+2, 4t+3\} \end{aligned}
It is easily seen that these three subsets are disjoint and that the sum of elements in each set is 9t+6 9t+6 .

Claim 2. Each Yj={(2j+1)k+1,,(2j+1)k+2k} Y_j = \{(2j+1)k+1, \ldots, (2j+1)k+2k\} can be partitioned into k k disjoint subsets, each having 2 elements and the same sum.

Proof. The obvious partitioning works:
Yj={(2j+1)k+1,(2j+1)k+2k}{(2j+1)k+k,(2j+1)k+(k+1)}. Y_j = \{(2j+1)k+1, (2j+1)k+2k\} \cup \cdots \cup \{(2j+1)k+k, (2j+1)k+(k+1)\}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.