Могло ли получиться три одинаковых числа?

[Ktina]

На доске написано 100 различных натуральных чисел. К каждому из этих чисел прибавили НОД всех остальных. Могло ли среди 100 чисел, полученных в результате этих действий, оказаться три одинаковых?

(автор задачи — С. Берлов)

[gris]

два одинаковых получаются просто. берём сто первых простяшек, и все, кроме двойки и тройки, умножаем на шесть. Получаем две пятёрки в начале. А если всё это дело умножить на тринадцать, то ничего не изменится.

[Ktina]

gris
А три не могут, осталось это доказать.

[gris]

если есть три хороших числа, то остальные заменим на одно, равное их НОДу.

[Dendr]

gris в сообщении #1417922 писал(а):

если есть три хороших числа, то остальные заменим на одно, равное их НОДу.

Продолжая эту мысль: если домножить его на произведение трех плюс единица, то все четыре числа будут различными. Тогда задача сводится к нахождению семи взаимно простых чисел, которые формируют упомянутую четверку:
$apq, bpr, cqr, dpqr$
Вообще говоря, потребуется попарная взаимная простота только у чисел $p, q, r$, прочие могут, попарно, иметь общие делители, но только не в тройках.

По условию, $apq+r=bpr+q=cqr+p$. Следовательно, $p=q (\bmod r), p=r (\bmod q), q=r (\bmod p)$
Для определенности, но без ограничения общности, можем считать, что $p>q>r>0$.
Следовательно, $q=r$. Противоречие.

Для двух чисел (хоть из ста, хоть из трех), как легко убедиться такими же рассуждениями, необходимо пять чисел: $ap, bq, cpq$. Тогда $ap+q=bq+p; (a-1)p=(b-1)q$. Как видно, здесь решение есть: мы можем использовать два любых взаимно простых числа $p, q$, тогда набор $p+npq, q+npq, \left\lbrace mpq\right\rbrace$, где $n, m$ - произвольные целые, отвечает требуемому условию.
Например, $p=21, q=100, n=2: 4221, 4300, 2100, 4200, 6300, 8400, ...$ НОД всех, кроме второго, равен 21, всех, кроме первого - 100. В итоге в конечном наборе возникнут два числа 4321.