Решение задачи 238

Условие:

Петя выбрал 10 последовательных натуральных чисел и записал каждое из них красным или синим карандашом (каждый цвет присутствует). Могла ли сумма НОК всех красных чисел и НОК всех синих чисел заканчиваться на 2016? НОК - это наименьшее общее кратное набора натуральных чисел, то есть наименьшее натуральное число, которое делится на все числа этого набора.

Решение:

Сначала нужно заметить, что если некоторое число заканчивается на 2016, то оно делится на 16.

Действительно, если число заканчивается на 2016, то его можно представить в виде k*10⁵ + 2016, для некоторого натурального k. 10⁵ и 2016 делятся на 16, значит и всё число делится на 16.

Заметим, что среди любых 10 подряд идущих чисел максимум два кратны 8.

Если нашлось только одно число, кратное 8, то без ограничения общности будем считать, что оно написано красным цветом. В этом случае НОК синих чисел не будет делиться на 8, т.к. ни одно из синих чисел не делится на 8. А НОК красных чисел будет делиться на 8, т.к. есть число, кратное 8. Значит сумма этих НОК не будет кратна 8, и уж тем более 16.

Если же нашлось два числа, кратных 8, то только одно из них кратно 16. Пусть A - это число, кратное 8, но не кратное 16, а B - это число, кратное 16.

Если А и B покрашены в один цвет (допустим, в красный), то НОК красных чисел кратен 16, а НОК синих -- нет. Значит их сумма не кратна 16.

Если же А и В покрашены в разные цвета (допустим, А -- в красный, а В -- в синий), то НОК синих чисел кратен 16, а НОК красных -- нет. Опять получаем, что их сумма не может быть кратна 16.

Получается, что в любом случае сумма НОК красных и синих чисел не может быть кратна 16, значит не может заканчиваться на 2016.

Ответ:

Нет, не может.