Problem 1495

1. **Define the set $D$ and the subset $S$:**
Let $D$ be the set of all pairs $(i, j)$ where $1 \le i, j \le n$. We need to find a subset $S \subset D$ such that $|S| \ge \left\lfloor \frac{3n(n+1)}{5} \right\rfloor$ and for any $(x_1, y_1), (x_2, y_2) \in S$, we have $(x_1 + x_2, y_1 + y_2) \notin S$.

2. Choose an anti-diagonal strip:
Define $m := \left\lfloor \frac{4n + 6}{5} \right\rfloor$. We choose the subset $S$ as:
$$S = \{(i, j) \in D \mid m \le i + j < 2m\}$$
This subset $S$ is chosen such that it forms an anti-diagonal strip in the $n \times n$ grid.

3. **Verify that $S$ is sum-free:**
For any $(x_1, y_1), (x_2, y_2) \in S$, we have:
$$m \le x_1 + y_1 < 2m \quad \text{and} \quad m \le x_2 + y_2 < 2m$$
Adding these inequalities, we get:
$$2m \le (x_1 + y_1) + (x_2 + y_2) < 4m$$
Since $(x_1 + x_2, y_1 + y_2)$ would have a sum $x_1 + y_1 + x_2 + y_2$ that is at least $2m$ and less than $4m$, it cannot lie within the range $m \le i + j < 2m$. Therefore, $S$ is sum-free.

4. **Calculate the size of $S$:**
The size of $S$ can be calculated by counting the number of pairs $(i, j)$ such that $m \le i + j < 2m$. This is equivalent to counting the number of lattice points in the region between the lines $i + j = m$ and $i + j = 2m - 1$.

The total number of pairs in $D$ is $n^2$. The number of pairs $(i, j)$ such that $i + j < m$ is given by the sum of the first $m-1$ integers:
$$\binom{m-1}{2} = \frac{(m-1)(m-2)}{2}$$
Similarly, the number of pairs $(i, j)$ such that $i + j \ge 2m$ is given by the sum of the first $2n - 2m + 1$ integers:
$$\binom{2n - 2m + 2}{2} = \frac{(2n - 2m + 2)(2n - 2m + 1)}{2}$$
Therefore, the size of $S$ is:
$$|S| = n^2 - \binom{m-1}{2} - \binom{2n - 2m + 2}{2}$$

5. Verify the bound:
We need to show that:
$$|S| \ge \left\lfloor \frac{3n(n+1)}{5} \right\rfloor$$
By substituting $m = \left\lfloor \frac{4n + 6}{5} \right\rfloor$ and simplifying the expressions, it can be shown that the size of $S$ meets the required bound for all $n$.

This completes the proof that such a subset $S$ exists.

$\blacksquare$