ВсОШ 2023, 8 класс, задача 7
( баллов) Сколько существует способов расположить в ряд крестиков и ноликов так, чтобы среди любых трёх подряд идущих значков нашёлся хотя бы один нолик, если
(а) ( балла) ;
(б) ( балла) ?
Ответ
Ответ: (а) ; (б) .
Решение. Пронумеруем нолики слева направо числами от до . Обозначим количество крестиков перед первым ноликом через , между первым и вторым ноликом — через , , после тринадцатого нолика — через . Получаем, что . То, что среди любых трёх подряд идущих значков есть хотя бы один нолик, эквивалентно тому, что три крестика не могут идти подряд, то есть для любого . Заметим, что подходящие последовательности крестиков и ноликов взаимно однозначно сопоставляются последовательностям , , , с указанными условиями.
(а) Сумма целых неотрицательных чисел равна , причём каждое из них не больше . Это означает, что какое-то одно должно быть равно , а все остальные должны быть равны . Так как может принимать любое значение от до , получаем, что вариантов ровно .
(б) Теперь сумма целых неотрицательных чисел равна . Это означает, что либо какое-то равно , а все остальные равны , либо какие-то и равны , а все остальные равны . В первом случае получаем вариантов. Во втором случае получаем вариант, ведь нам нужно выбрать индекса из возможных.
Итого получаем ровно вариантов.
Верное решение пункта (а).
Верное решение пункта (б).