Library / /212 of 397

, 2022

Combinatorics Difficulty 5.9 AIME, harder Prove it Taiwan

Let $n, s, t$ be three positive integers, and let $A_1, \dots, A_s, B_1, \dots, B_t$ be subsets (not necessarily distinct) of $\{1, 2, \dots, n\}$ . For any subset $S$ of $\{1, \dots, n\}$ , we define $f(S)$ to be the number of $i \in \{1, \dots, s\}$ satisfying $S \subseteq A_i$ ; and $g(S)$ to be the number of $j \in \{1, \dots, t\}$ satisfying $S \subseteq B_j$ . Suppose that for any $1 \le x < y \le n$ , $f(\{x, y\}) = g(\{x, y\})$ holds.
Prove: if $t < n$ , then there must exist $1 \le x \le n$ such that $f(\{x\}) \ge g(\{x\})$ .

Solution

Suppose for the sake of contradiction that $t < n$ and $f(\{x\}) < g(\{x\})$ for any $1 \le x \le n$ . Let $c_1, \dots, c_n$ be some real numbers, and for any $S \subseteq [n]$ let $c(S)$ be the expression
$\sum_{i \in S} c_i .$
Then clearly
$\sum_{i=1}^{s} c(A_i)^2 = \sum_{j=1}^{t} c(B_j)^2 - \sum_{x=1}^{n} (g(\{x\}) - f(\{x\}))c_x^2$
Since $t < n$ , there exists $(c_1, \dots, c_n) \ne (0, \dots, 0) \in \mathbb{R}^n$ such that $c(B_j) = 0$ for any $j = 1, \dots, t$ . With this $(c_1, \dots, c_n)$ , we have
$\sum_{i=1}^{s} c(A_i)^2 = - \sum_{x=1}^{n} (g(\{x\}) - f(\{x\}))c_x^2 < 0$
as $g(\{x\}) - f(\{x\}) > 0$ for any $x \in [n]$ . This is clearly a contradiction. Thus there must be some $x \in [n]$ with $f(\{x\}) \ge g(\{x\})$ .

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 translated into English from zh; metadata (topic, difficulty) added by this project.