Maths Olympiad Prep

Library / /17 of 18

Combinatorics Difficulty 8.6 Shortlist Prove it Balkan Mathematical Olympiad

Let M={1,2,,2013}M = \{1, 2, \dots, 2013\} and let Γ\Gamma be a circle. For every nonempty subset A\mathcal{A} of the set MM, denote by S(A)S(\mathcal{A}) the sum of elements of the set A\mathcal{A}, and define S()=0S(\emptyset) = 0 (\emptyset is the empty set). Is it possible to join every subset A\mathcal{A} of MM with some point AA on the circle Γ\Gamma so that following conditions are fulfilled:
1. Different subsets are joined with different points;
2. All joined points are vertices of a regular polygon;
3. If A1,A2,,AkA_1, A_2, \dots, A_k are some of the joined points, k>2k > 2, such that A1A2AkA_1A_2 \dots A_k is a regular kk-gon, then 2014 divides S(A1)+S(A2)++S(Ak)S(\mathcal{A}_1) + S(\mathcal{A}_2) + \dots + S(\mathcal{A}_k)?

Solution

We will prove that this is possible. Total number of subsets of the set MM is 220132^{2013}. On circle Γ\Gamma we arbitrarily choose 220132^{2013} points which are vertices of a regular 220132^{2013}-gon. We join subsets of the set MM and chosen points in the following manner: if we join subset A\mathcal{A} with some point on Γ\Gamma, we join subset Ac=MA\mathcal{A}^c = M\setminus \mathcal{A} with a point symmetric to the point joined with A\mathcal{A} with respect to the center of Γ\Gamma (number 220132^{2013} is even, so this is possible). If A1,A2,,AkA_1, A_2, \dots, A_k are some of the points joined with subsets, which are vertices of a regular kk-gon, then it follows that k22013k\mid 2^{2013}, so kk is a number divisible by 44, say k=4tk = 4t. That is why all points A1,A2,,AkA_1, A_2, \dots, A_k can be divided in k2=2t\frac{k}{2} = 2t pairs of symmetric points with respect to center of Γ\Gamma. Using that
S(A)+S(Ac)=1+2++2013=10072013, S(\mathcal{A}) + S(\mathcal{A}^c) = 1 + 2 + \dots + 2013 = 1007 \cdot 2013,
we get S(A1)++S(Ak)=2t10072013=20142013tS(\mathcal{A}_1) + \dots + S(\mathcal{A}_k) = 2t \cdot 1007 \cdot 2013 = 2014 \cdot 2013 \cdot t, so all conditions are fulfilled.

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.