Library / Ukrainian National Mathematical Olympiad, Third Round, First Tour /11 of 19

Ukrainian National Mathematical Olympiad, Third Round, First Tour

Number theory Difficulty 5.6 AIME, harder Prove it Ukraine

In one magic country there are only banknotes of nominal 3, 25 and 80 hryvnyas. Businessman Victor ate in a restaurant of this country for 2024 days in a row, and each day he paid (without change) exactly 1 hryvnya more than the previous one. Is it possible that he paid exactly a million banknotes?

Solution

Suppose that he paid the sum of $S$ UAH with $k$ banknotes, among which there are $a$ of 3 UAH, $b$ of 25 UAH, and $c$ of 80 UAH. Then
$S = 3a + 25b + 80c \equiv 3a + 3b + 3c = 3k \pmod{11}.$
If $n+1$ is the sum that he paid in the first day, then in the $i$ -th day he paid a sum of $n+i$ with precisely $k_i$ banknotes. From the above formula it follows that $3(k_1 + k_2 + \cdots + k_{2024}) \equiv (n+1) + (n+2) + \cdots + (n+2024) = 2024n + 1012 \cdot 2025 \pmod{11}$ .
As $1012 \equiv 11$ , the right side is divisible by 11, so the left side, equal to the total number of pair banknotes, also is divisible by 11. But the number 1000000 isn't divisible by 11, so Victor couldn't have used exactly a million banknotes.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.