Competition problem — Algebra — Maths Olympiad Prep

Library / /32 of 87

Algebra Difficulty 6.1 National Olympiad Prove it Russia

On the board 777 pairwise distinct complex numbers are written. It turned out that there are exactly 760 ways to choose a pair of numbers $a$ and $b$ written on the board so that
$a^2 + b^2 + 1 = 2ab.$

(Here pairs considered unordered, i.e., $(a, b)$ and $(b, a)$ is the same pair.) Prove that one can choose numbers $c$ and $d$ written on the board such that
$c^2 + d^2 + 2025 = 2cd.$

Solution

Note that the condition $a^2 + b^2 + 1 = 2ab$ is equivalent to $(a-b)^2 = -1$ or $a-b = \pm i$ . Consider a graph whose vertices are the numbers written on the board, with an edge connecting two numbers if they differ by $i$ . According to the problem's condition, this graph has exactly 760 edges.

Each connected component of this graph forms a path consisting of numbers of the form $z, z+i, z+2i, \dots, z+(n-1)i$ . Suppose the graph has $k$ connected components. Then it contains $777-k$ edges, so $k=17$ .

Since $17 \cdot 45 = 765 < 777$ , at least one connected component must have at least 46 vertices. Therefore, there exist two numbers in this component, say $c$ and $d = c + 45i$ . Then $(c-d)^2 = 45^2 \cdot i^2 = -2025$ , which implies $c^2 + d^2 + 2025 = 2cd$ , as required.

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.