ВсОШ 2026, 10 класс, задача 6
( баллов) При каком наименьшем во все клетки таблицы можно расставить некоторые из чисел от до , каждое не более одного раза, так, чтобы любые два соседние по горизонтали или вертикали числа отличались хотя бы в раза?
Ответ
Ответ: .
Решение. Поскольку в таблице всего клеток, то . Предположим, что . Тогда каждое число используется ровно раз.
Покрасим клетки доски в шахматную раскраску. Заметим, что никакие два из чисел от до не могут стоять рядом. А так как их всего , то они должны целиком занимать либо все белые клетки, либо все чёрные. Действительно, всю доску без любого прямоугольника можно разбить на прямоугольники (см. рисунок), и тогда если в каком-то из них нет чисел от до , то в каком-то будет таких числа, противоречие. А если в каждом прямоугольнике есть ровно одно из этих чисел, то они занимают либо все белые клетки, либо все чёрные.
Тогда числа от до будут занимать все клетки другого цвета. Значит, рядом с числом будут хотя бы числа от до , т.е. числа, большие . Но оба они не смогут быть хотя бы в раза больше чем число . Значит, при так сделать не получится.
На рисунке нарисован пример для .
Верное решение.