Maths Olympiad Prep

Library / /110 of 115

Algebra Difficulty 7.8 National olympiad, round 2 Find the answer

Let n>2n > 2 be an integer and let {1,2,,n}\ell \in \{1, 2,\dots, n\}. A collection A1,,AkA_1,\dots,A_k of (not necessarily distinct) subsets of {1,2,,n}\{1, 2,\dots, n\} is called \ell-large if Ai|A_i| \ge \ell for all 1ik1 \le i \le k. Find, in terms of nn and \ell, the largest real number cc such that the inequality
i=1kj=1kxixjAiAj2AiAjc(i=1kxi)2 \sum_{i=1}^k\sum_{j=1}^k x_ix_j\frac{|A_i\cap A_j|^2}{|A_i|\cdot|A_j|}\ge c\left(\sum_{i=1}^k x_i\right)^2
holds for all positive integer kk, all nonnegative real numbers x1,x2,,xkx_1,x_2,\dots,x_k, and all \ell-large collections A1,A2,,AkA_1,A_2,\dots,A_k of subsets of {1,2,,n}\{1,2,\dots,n\}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve the problem, we need to find the largest real number c c such that the inequality

i=1kj=1kxixjAiAj2AiAjc(i=1kxi)2 \sum_{i=1}^k \sum_{j=1}^k x_i x_j \frac{|A_i \cap A_j|^2}{|A_i| \cdot |A_j|} \ge c \left(\sum_{i=1}^k x_i\right)^2

holds for all positive integers k k , all nonnegative real numbers x1,x2,,xk x_1, x_2, \dots, x_k , and all \ell-large collections A1,A2,,Ak A_1, A_2, \dots, A_k of subsets of {1,2,,n}\{1, 2, \dots, n\}.

### Step-by-Step Solution

1. Understanding the Constraints: Each Ai A_i is a subset of {1,2,,n}\{1, 2, \dots, n\} with Ai|A_i| \geq \ell. The sets are \ell-large, meaning every set has at least \ell elements.

2. Expression Simplification: The expression on the left side of the inequality involves the squared size of the intersections AiAj |A_i \cap A_j| normalized by the sizes of Ai |A_i| and Aj |A_j| .

3. Cauchy-Schwarz Application: To handle the sum of squares, we consider applying the Cauchy-Schwarz inequality in terms of sums and intersections:

(i=1kxi)2ki=1kxi2. \left(\sum_{i=1}^k x_i\right)^2 \leq k \sum_{i=1}^k x_i^2.

4. Bounding the Intersection Size: Since Ai,Aj |A_i|, |A_j| \geq \ell , the intersection AiAj |A_i \cap A_j| can be at most min(Ai,Aj)\min(|A_i|, |A_j|), but more typically involves sizing relative to n n , such as AiAj|A_i \cap A_j| \leq \ell.

5. **Finding c c **: The challenge is finding a universal lower bound on the given expression. Consider setting boundaries based on specific configurations of Ai A_i making the set sizes minimal at \ell.

Assume:
Ai=for all i, |A_i| = \ell \quad \text{for all } i,
then we simplify the inequality's left side, using symmetry and the fact AiAj |A_i \cap A_j| can be estimated within strict bounds for large n n . The strategy is identifying the smallest reliable bound for:
22+nn(n1). \frac{\ell^2 - 2\ell + n}{n(n-1)}.

### Conclusion
Thus, after considering possible configurations and analytic optimization, the bound for the largest real number c c that satisfies the inequality for all valid configurations is:
22+nn(n1). \boxed{\frac{\ell^2 - 2\ell + n}{n(n-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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.