Maths Olympiad Prep

Library / /454 of 520

Combinatorics Difficulty 6.1 National olympiad Prove it

Example 2 Suppose in Example 1, the maximum number of elements is f(n)f(n). Prove:
16(n24n)f(n)16(n2n). \frac{1}{6}\left(n^{2}-4 n\right) \leqslant f(n) \leqslant \frac{1}{6}\left(n^{2}-n\right) .

Solution

First, estimate the upper bound of f(n)f(n), i.e., prove the right inequality in (2).
Each three-element subset {i,j,k}\{i, j, k\} contains three two-element subsets {i,j}\{i, j\}, {j,k}\{j, k\}, {i,k}\{i, k\}.

Since every two elements (three-element subsets of XX) in A\mathscr{A} have at most one common element, the two-element subsets contained in each pair of three-element subsets are all different.
The two-element subsets of XX total Cn2C_{n}^{2}, so
3f(n)Cn2, 3 f(n) \leqslant C_{n}^{2},

i.e.,
f(n)13Cn2=n2n6. f(n) \leqslant \frac{1}{3} C_{n}^{2}=\frac{n^{2}-n}{6} .

To estimate the lower bound of f(n)f(n), the construction method should be used. Construct a batch of three-element subsets, the number of which is 16n(n4)\geqslant \frac{1}{6} n(n-4), and each pair of them has at most one common element.
For this purpose, consider all three-element subsets {i,j,k}\{i, j, k\} that satisfy the condition
i+j+k0(modn) i+j+k \equiv 0 \quad(\bmod n)
(i.e., i+j+ki+j+k is divisible by nn).
If i=ij=ji^{\prime}=i \cdot j^{\prime}=j, and
i+j+ki+j+k0(modn), i^{\prime}+j^{\prime}+k^{\prime} \cong i+j+k \equiv 0 \quad(\bmod n),

then
kk(modn). k^{\prime} \equiv k \quad(\bmod n) .

When k,k{1,2,,n}k^{\prime}, k \in\{1,2, \cdots, n\}, (4) is k=kk^{\prime}=k. Therefore, every two (different) three-element subsets that satisfy (3) have at most one common element.
Now, calculate the number ss of three-element subsets {i,j,k}\{i, j, k\} that satisfy (3).
First, choose ii, which has nn choices. After ii is chosen, choose j,jij, j \neq i, and jj does not satisfy the congruence equation
2i+j=0(modn) 2 i+j=0 \quad(\bmod n)
(i.e., when 2i<n2 i<n, jn2ij \neq n-2 i; when 2in2 i \geqslant n, j2n2ij \neq 2 n-2 i) and
i+2j0(modn) i+2 j \equiv 0 \quad(\bmod n)
(i.e., jni2,j2ni2)\left.j \neq \frac{n-i}{2}, j \neq \frac{2 n-i}{2}\right). Therefore, jj has at least n4n-4 choices. After ii and jj are determined, kk is also determined by (3), and is different from ii and jj. Therefore, s16n(n4)s \geqslant \frac{1}{6} n(n-4). Thus, the other half of (2) holds.

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.