Maths Olympiad Prep

Library / Mongolian Mathematical Olympiad Round 3 /9 of 12

Mongolian Mathematical Olympiad Round 3

Combinatorics Difficulty 6.2 National Olympiad Prove it Mongolia

21 points divide a circle into 21 arcs of equal length. How many sets of 7 points, where no two points have 3 unit or 7 unit arc distance, are there?

Solution

Answer: 126.
Let 1,2,3,…,211, 2, 3, \ldots, 21 be points on a circle in clockwise order and let us use the following notation.
a1=1,a2=8,a3=15b1=4,b2=11,b3=18c1=7,c2=14,c3=21d1=10,d2=17,d3=3e1=13,e2=20,e3=6f1=16,f2=2,f3=9g1=19,g2=5,g3=12 \begin{aligned} a_1 &= 1, & a_2 &= 8, & a_3 &= 15 \\ b_1 &= 4, & b_2 &= 11, & b_3 &= 18 \\ c_1 &= 7, & c_2 &= 14, & c_3 &= 21 \\ d_1 &= 10, & d_2 &= 17, & d_3 &= 3 \\ e_1 &= 13, & e_2 &= 20, & e_3 &= 6 \\ f_1 &= 16, & f_2 &= 2, & f_3 &= 9 \\ g_1 &= 19, & g_2 &= 5, & g_3 &= 12 \end{aligned}

Then we can take only one aia_i. This means the seven points must be ai,bj,ck,dl,em,fn,gta_i, b_j, c_k, d_l, e_m, f_n, g_t. In order to not have 3 unit arc distance, we must have
i≠j,j≠k,k≠l,l≠m,m≠n,n≠t,t≠i.i \neq j, j \neq k, k \neq l, l \neq m, m \neq n, n \neq t, t \neq i.
The total occurrence number of ai,bj,ck,dl,em,fn,gta_i, b_j, c_k, d_l, e_m, f_n, g_t is 373^7.
Now let us use inclusion-exclusion principle, to count an occurrence numbers at least one index is equal. Let A1A_1 be the set of all occurrences with i=ji = j. Let A2A_2 be the set of all occurrences with j=kj = k, et cetera, and let A7A_7 be the set of all occurrences with t=it = i. Then we have
∣A1∪A2∪⋯∪A7∣=∑∣Ai∣−∑∣Ai∩Aj∣+⋯−∣A1∩A2∩⋯∩A7∣. |A_1 \cup A_2 \cup \cdots \cup A_7| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots - |A_1 \cap A_2 \cap \cdots \cap A_7|.
Here we have
∑∣Ai∣=C71⋅36∑∣Ai∩Aj∣=C72⋅35∑∣Ai∩Aj∩Ak∣=C73⋅34∑∣Ai∩Aj∩Ak∩Al∣=C74⋅33∑∣Ai∩Aj∩Ak∩Al∩Am∣=C75⋅32∑∣Ai∩Aj∩Ak∩Al∩Am∩An∣=C76⋅3∣A1∩A2∩⋯∩A7∣=3. \begin{align*} \sum |A_i| &= C_7^1 \cdot 3^6 \\ \sum |A_i \cap A_j| &= C_7^2 \cdot 3^5 \\ \sum |A_i \cap A_j \cap A_k| &= C_7^3 \cdot 3^4 \\ \sum |A_i \cap A_j \cap A_k \cap A_l| &= C_7^4 \cdot 3^3 \\ \sum |A_i \cap A_j \cap A_k \cap A_l \cap A_m| &= C_7^5 \cdot 3^2 \\ \sum |A_i \cap A_j \cap A_k \cap A_l \cap A_m \cap A_n| &= C_7^6 \cdot 3 \\ |A_1 \cap A_2 \cap \cdots \cap A_7| &= 3. \end{align*}
Hence, the number of configurations satisfying the condition is
37−C71⋅36+C72⋅35−C73⋅34+C74⋅33−C75⋅32+C76⋅3−3=(3−1)7−2=126. 3^7 - C_7^1 \cdot 3^6 + C_7^2 \cdot 3^5 - C_7^3 \cdot 3^4 + C_7^4 \cdot 3^3 - C_7^5 \cdot 3^2 + C_7^6 \cdot 3 - 3 = (3-1)^7 - 2 = 126.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.