<< к заданиям
Всероссийская олимпиада школьников по математике, 8 класс, 2022 год, 3 этап
дата проведения: 30 ноября 2022

Задача 7.

Сколько существует способов расположить в ряд 𝑛 крестиков и 13 ноликов так, чтобы среди любых трёх подряд идущих значков нашёлся хотя бы один нолик, если

  1. 𝑛 = 27
  2. 𝑛 = 26

Ответ на Задачу 7.

Ответ: а) 14. б) 105.

Решение:

Пронумеруем нолики слева направо числами от 1 до 13. Обозначим количество крестиков перед первым ноликом через $a_1$, между первым и вторым ноликом – через $a_2$, $\ldots$, после тринадцатого нолика – через $a_{14}$. Получаем, что $a_1 + a_2 + \ldots + a_{14} = n$. То, что среди любых трёх подряд идущих значков есть хотя бы один нолик, эквивалентно тому, что три крестика не могут идти подряд, то есть $a_i\leqslant2$ для любого $i$ = 1, $2$, $\ldots$, $14$. Заметим, что подходящие последовательности крестиков и ноликов взаимно однозначно сопоставляются последовательностям $a_1$, $a_2$, $\ldots$, $a_{14}$ с указанными условиями.

a) Сумма 14 целых неотрицательных чисел равна 27, причём каждое из них не больше 2. Это означает, что какое-то одно $a_i$ должно быть равно 1, а все остальные должны быть равны 2. Так как $i$ может принимать любое значение от 1 до 14, получаем, что вариантов ровно 14.

б) Теперь сумма 14 целых неотрицательных чисел равна 26. Это означает, что либо какоето $a_i$ равно 0, а все остальные равны 2, либо какие-то $a_j$ и $a_k$ равны 1, а все остальные равны 2. В первом случае получаем 14 вариантов. Во втором случае получаем $\displaystyle \mathrm{C}_{14}^2 = \frac{14⋅13}{2} = $ 91 вариант, ведь нам нужно выбрать 2 индекса из 14 возможных.

Итого получаем ровно 14 + 91 = 105 вариантов.