Maths Olympiad Prep

Library / /9 of 12

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
ij,jk,kl,lm,mn,nt,ti.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
A1A2A7=AiAiAj+A1A2A7. |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=C7136AiAj=C7235AiAjAk=C7334AiAjAkAl=C7433AiAjAkAlAm=C7532AiAjAkAlAmAn=C763A1A2A7=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
37C7136+C7235C7334+C7433C7532+C7633=(31)72=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,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.