Library / /11 of 96

, 2021

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Baltic Way

$A$ is a 20-element set of residue classes modulo $397$ . Prove that for any non-negative integer $n$ there exist $x_1, x_2, x_3, x_4 \in A$ , such that $x_1 \neq x_2$ and
$(x_1 - x_2)n \equiv x_3 - x_4 \pmod{397}$

Solution

Observe that $397$ is a prime. If $n$ is divisible by $397$ , the statement is trivial.

Fix an arbitrary positive integer $n$ not divisible by $397$ . If for $x_1, x_2, x_3, x_4 \in A$ , where $(x_1, x_4)$ and $(x_2, x_3)$ are different ordered pairs, we have
$x_1 n + x_4 \equiv x_2 n + x_3 \pmod{397},$
then we are done (if $x_1 = x_2$ then $x_3 = x_4$ due to this equivalence).

Otherwise, this equivalence is impossible and therefore a map $(a, b) \mapsto an + b$ is an injective map from $A \times A$ to $\mathbb{Z}_{397}$ . But this is impossible since the number of elements in $A \times A$ is $400 > 397$ . $\square$

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.