ВсОШ 2023, 9 класс, задача 3
( баллов) Каждое натуральное число, большее , окрасили либо в красный, либо в синий цвет. Оказалось, что произведение любых двух различных красных чисел - синее. Может ли случиться, что никакие два синих числа не отличаются на ? (С. Берлов)
Ответ. Не может.
Первое решение. Предположим, что это возможно.
Лемма. Пусть число синее; тогда - красное.
Доказательство. Поскольку синее, числа и красные, иначе два синих числа отличаются на . Поэтому число синее. Значит, красное.
Очевидно, что существует синее число ; по лемме число красное. Рассмотрим два случая.
Пусть число синее. Тогда по лемме число красное. Поскольку , и числа и красные, то число обязано быть синим. По лемме число красное, но оно является произведением красных чисел и . Этого не может быть.
Пусть теперь число красное. Тогда число синее, и по лемме число красное. Поскольку и числа и красные, числа и должны быть синими, а тогда, по лемме, числа и красные. Но тогда красное число равно произведению красных чисел и . Противоречие.
Второе решение. Опять же предположим противное.
Начнём со следующего замечания. Пусть и - два различных красных числа; тогда число тоже красное. Действительно, по условию число синее, а тогда красное.
Цвета чисел не могут строго чередоваться - иначе все числа одной чётности будут красными, а тогда найдутся и два красных числа с красным произведением. Значит, есть два одноцветных числа, отличающихся на - пусть это и . Из условия их общий цвет - красный.
Из замечания выше получаем сначала, что число красное, а затем - что число тоже красное. Значит, по условию, число синее.
С другой стороны, из того же замечания число красное. Значит, по условию, число тоже синее. Итак, мы нашли два соседних синих числа и , что невозможно.