, 2010

Combinatorics Difficulty 4.8 AIME Prove it Romania

Let $D := \{1, 2, \dots, n\} \times \{1, 2, \dots, n\}$ . Prove there exists a set $S \subset D$ with $|S| \ge \lfloor \frac{3}{5}n(n+1) \rfloor$ , such that for any $(x_1, y_1), (x_2, y_2) \in S$ we have $(x_1 + x_2, y_1 + y_2) \notin S$ .

Solution

It is easy to find a weaker bound of $|S| = n\lfloor\frac{1}{2}n\rfloor$ by taking $S = \{(x, y) \in D \mid x > n/2\}$ . To find the bound asked, we need look at the diagonals of the tableau!

Diagram for the selection $\bullet$ of $S_u$ (exact for $n = 13$ ).

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.