IMC 2019 · Day 2 · P8

Choose disctint sets $I_1, \dots, I_A \subset \{1, 2, \dots, n\}$ where $A \ge 1.8^n$, and let $J_1, \dots, J_B \subset \{1, 2, \dots, n\}$ be all sets so that $S(J_i) = 2019$; for the sake of contradiction, assume that $B \ge 1.7^n$.

Every set $I \subset \{1, 2, \dots, n\}$ can be identified with a $0-1$ vector of length $n$: the $k$th coordinate in the vector is 1 if $k \in I$. Then $s(I) = \langle I, X \rangle$, where $X = (x_1, \dots, x_n)$ and $\langle \cdot, \cdot \rangle$ stands for the usual scalar product.

For all ordered pairs $(a, b) \in \{1, \dots, A\} \times \{1, \dots, B\}$ consider the vector $I_a - J_b \in \{-1, 0, 1\}^n$. By the pigeonhole principle, since $AB \ge (1.8 \cdot 1.7)^n > 3^n$, there are two pairs $(a, b)$ and $(c, d)$ such that $I_a - J_b = I_c - J_d$. Multiplying this by $X$ we get $s(I_a) - 2019 = s(I_c) - 2019$; that implies $a = c$. But then $J_b = J_d$, that is, $b = d$, and our pairs coincide. Contradiction.