Track / Stage 6 / 67 of 400 #1067 of 2000

Problem 1067

National olympiad, first round

Combinatorics Difficulty 6.1 Prove it

Problem 11.3. Given an orthogonal coordinate system with origin $O$ in the plane. Distinct real numbers are written at the points with integer coordinates. Let $A$ be a nonempty finite set of integer points which is central-symmetric regarding $O$ and $O \notin A$ . Prove that there exists an integer point $X$ such that if $A_{X}$ is the image of $A$ under translation defined by $\overrightarrow{O X}$ , then at least half of the numbers written at the points of $A_{X}$ are greater than the number written at $X$ .

Avgustin Marinov

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Solution: Let us denote the number of points in $A$ , which is obviously even, by $2 s$ . Connect all integer points $X$ with the points from $A_{X}$ by arrows so that the arrow points to the smaller number. Suppose no point $X$ with the required property exists. Then there are at least $s+1$ arrows pointing out of any point $X$ . For every natural
number $n$ denote the square with vertices $(n, n),(-n, n),(-n,-n)$ and $(n,-n)$ by $K_{n}$ .

Since $A$ is a finite set, there exists a natural number $d$ such that $A \subset K_{d}$ . For every $n$ denote the number of arrows within the square $K_{n}$ by $S_{n}$ . Since there are at least $s+1$ arrows pointing out of every integer point of $K_{n}$ (and these arrows are within the square $K_{n+d}$ ), it follows that $(2 n+1)^{2}(s+1) \leq S_{n+d}$ . On the other hand, since $A_{X}$ is a central-symmetric set, there are at most $s-1$ arrows pointing to every integer point of $K_{n+d}$ . Therefore $S_{n+d} \leq(2 n+2 d+1)^{2}(s-1)$ . Thus $(2 n+1)^{2}(s+1) \leq(2 n+2 d+1)^{2}(s-1)$ , so $s+1 \leq(1+$ $\left.\frac{2 d}{2 n+1}\right)^{2}(s-1$ ) for any $n$ . When $n \rightarrow \infty$ one obtains $s+1 \leq s-1$ , a contradiction. Therefore a point $X$ with the required property does exist.

## WINTER MATHEMATICAL COMPETITION

## Grade 8 - First Group.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.