Пусть $a$, $b$, $c$ — целые положительные числа, каждые два из которых взаимно просты. Докажите, что наибольшее из целых чисел, не представимых в виде
$$
xbc+yca+zab
$$
(где $x$, $y$, $z$ — неотрицательные целые числа), равно
$$
2abc-ab-bc-ca.
$$
Международная математическая олимпиада школьников (XXIV, 1983 год)
Пусть$a_1$, $a_2$, $\ldots$, $a_n$ — натуральные попарно взаимно простые числа. Назовём натуральное число $u$ «красным», если его можно представить в виде
$$
m=a_1a_2\ldots a_n\left(\dfrac{x_1}{a_1}+\ldots+\dfrac{x_n}{a_n}\right),\tag1
$$
где$x_1$, $x_2$, $\ldots$, $x_n$ — целые неотрицательные числа, и «синим» — в противном случае. Каково наибольшее синее число?
(В нашей задаче $n=3$.)
Одно из самых коротких решений этой задачи опирается на следующие два утверждения:
любое целое число $u$ допускает единственное представление (1), где $x_1$, $x_2$, $\ldots$, $x_n$ — целые числа, причём $0\le x_2\le a_2-1$, $\ldots$, $0\le x_{n}\le a_n-1$, $x_1$ может быть любым (такое представление будем называть стандартным);
целое число $u$ является красным тогда и только тогда, когда в его стандартном представлении $x_1\ge0$.
Из последнего утверждения ясно, что наибольшее синее число $m$ имеет стандартное представление с $x_1=-1$, $x_2=a_2-1$, $\ldots$, $x_{n}=a_n-1$, т. е.
$$
m=a_1a_2\ldots a_n\left(n-1-\dfrac1{a_1}-\ldots-\dfrac1{a_n}\right).
$$
Докажем эти утверждения по индукции, начиная со случая $n=2$. В этом случае утверждение 1) превращается в следующую полезную лемму (обозначим $a_1=a$, $a_2=b$):
Если натуральные числа $a$ и $b$ взаимно просты, то любое целое число $u$ единственным образом представляется в виде
$$
u=bx+ay,\tag2
$$
где $x$ и $y$ — целые числа, $0\le y\le b-1$.
Для её доказательства заметим, что все остатки от деления на $b$ чисел $0$, $a$, $2a$, $\ldots$, $(b-1)a$ различны (в противном случае какое-то число вида $(k-l)a$, где $0\le k\lt l\le b-1$, делилось бы на $b$, что невозможно). Следовательно, ровно одно из них, $ay$, даёт такой же остаток, как и число $u$, т. е. $u-ay=bx$ при некоторых целых $x$ и $y$, $0\le y\le b-1$.
Утверждение 2) при $n=2$ почти очевидно: если число $u$ красное, т. е. имеет представление (2) с $x\ge0$, $y\ge0$, то и в его стандартном представлении коэффициент при $b$ будет неотрицателен (если $y=qb+r$, где $q\ge0$, $0\le r\le b-1$, то $u=bx+ay=b(x+aq)+ar$).
Таким образом, в случае $n=2$ наибольшим синим числом будет $m=b(-1)+a(b-1)=ab-a-b$.
Покажем теперь, как с помощью этой же леммы сделать переход от $n=2$ к $n=3$ (тем самым задача М837 будет решена; в общем случае переход от $n$ к $n+1$ совершается аналогично). Перепишем представление вида (1) числа $u$, как показано на полях. Поскольку $c$ и $ab$ взаимно просты, по лемме можно найти (причём единственным образом) целые $v$ и $z$, $0\le z\le c-1$, такие что $u=cv+abz$, а затем — $x$ и $y$, $0\le y\le b-1$, такие что $v=bx+ay$. Это доказывает утверждение 1) для $n=3$. Для доказательства 2) достаточно заметить, что красным $u$ отвечают красные $v$, а стандартному представлению $u$ соответствует стандартное представление $v$, в котором $x\ge0$.
На рисунке отмечены красные и синие числа для $a=2$, $b=3$, $c=5$; здесь $m=29$. Видно, что они располагаются симметрично относительно точки $\dfrac m2$: если $u$ — красное число, то $m-u$ — синее. Из нашего решения нетрудно вывести, что так будет и в общем случае (при любых $a$, $b$, $c$): красные числа — это всевозможные значения функции $u(x,y,z)=bcx+cay+abz$ на множестве точек пространства с целыми координатами $(x,y,z)$, где $x\ge0$, $0\le y\le b-1$, $0\le z\le c-1$, а синие — её значения на множестве $x\le-1$, $0\le y\le b-1$, $0\le z\le c-1$. Эти множества симметричны, а функция $u$ — линейная, поэтому и её значения на этих множествах расположены симметрично.
Было бы интересно исследовать аналогичные задачи для представлений целых чисел в виде $Ax+By+Cz$ с любыми взаимно простыми коэффициентами $A$, $B$, $C$.
