Задача 7.
Сколько существует способов расположить в ряд 𝑛 крестиков и 13 ноликов так, чтобы среди любых трёх подряд идущих значков нашёлся хотя бы один нолик, если
- 𝑛 = 27
- 𝑛 = 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 вариантов.