Library / /1 of 11

, 2015

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Mongolia

$S_n = \{(x, y) \in \mathbb{Z}^2 \mid 1 \le x, y \le 5n\}.$
A subset $A \subseteq S_n$ is said to be sumfree if
$(x_1, y_1), (x_2, y_2) \in A \implies (x_1 + x_2, y_1 + y_2) \notin A.$
Show that there exists a sumfree subset with at least $15n^2$ elements.

Solution

Let $A := \{(x, y) \in S_n \mid 4n+1 \le x+y \le 8n+1\}$ . Then it is clear that $A$ is sumfree.
Now we show that $|A| \ge 15n^2$ .

For $k \in \mathbb{Z}_{\ge 1}$ , we let $T_k := \{(x, y) \in S_n \mid x + y = k\}$ . Then it is easy to see that
$|T_k| = \begin{cases} k-1 & k \le 5n \\ 10n-k+1 & k \ge 5n+1. \end{cases}$

Since $A$ is the disjoint union of $T_k$ for $4n+1 \le k \le 8n+1$ , we have
$|A| = 4n + (4n + 1) + \dots + (5n - 1) + 5n + (5n - 1) + \dots + 2n = 15n^2 + 3n.$

Clearly $|A| \ge 15n^2$ .

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.