Track / Stage 6 / 90 of 400 #1090 of 2000

Problem 1090

National olympiad, first round

Number theory Difficulty 6.1 Prove it

9.1. Let $a_{1}, \ldots, a_{11}$ be distinct natural numbers, each not less than 2, whose sum is 407. Could it be that the sum of the remainders of some natural number $n$ when divided by the 22 numbers $a_{1}, a_{2}, \ldots, a_{11}, 4 a_{1}, 4 a_{2}, \ldots, 4 a_{11}$ equals 2012? (N. Agakhanov)

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

Answer: It cannot.

Solution: Suppose such a number $n$ exists.

Note that the maximum possible remainder when dividing by a natural number $m$ is $m-1$ . Therefore, the sum of the remainders when dividing any number by $a_{1}, \ldots, a_{11}$ is no more than $407-11=396$ , and the sum of the remainders when dividing it by $4 a_{1}, \ldots, 4 a_{11}$ is no more than $4 \cdot 407-11=1617$ . Thus, if all remainders were the maximum possible, their sum would be $396+1617=2013$ . Since this sum for our number $n$ is 2012, all remainders except one are the maximum possible, and one is one less than the maximum possible.

This means that for some $k$ , one of the remainders when dividing $n$ by $a_{k}$ and $4 a_{k}$ is the maximum possible, and the other is one less than the maximum possible. Then one of the numbers $n+1$ and $n+2$ is divisible by $a_{k}$ , and the other by $4 a_{k}$ , meaning two coprime numbers $n+1$ and $n+2$ are divisible by $a_{k} \geqslant 2$ . This is impossible.

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