К главе 21
21.1. Так как сосед справа и сосед слева неразличимы, то можно любого из сидящих оставить на месте, а остальных попросить пересесть на место, симметричное относительно того, кто остался на своем месте.
21.2. Обратить внимание на то, что, вычитая перестановки, в которых на первом месте стоит элемент а1, и перестановки, в которых на втором месте стоит элемент а2, мы некоторые перестановки вычтем дважды.
21.3. Поскольку в нашем распоряжении имеются семь разрядов, то выбрать места для трех двоек можно
21.4. Число не может начинаться с цифры 0. На сколько больше чисел мы получим, если не учтем это обстоятельство?
21.5. Экскурсантов для заселения первой каюты можно выбрать
21.6. Доказать, что
21.7. После упрощений мы придем к квадратному уравнению относительно n и k, которое нужно решить в целых числах. Удобнее решать это уравнение относительно k.
21.8. Все получившиеся после раскрытия скобок члены не будут подобными. Остается сосчитать их число.
21.9. Если n — 1 < k ? 2(n — 1), то члены, содержащие xk, могут быть получены лишь в результате перемножения членов суммы xk ? n + 1 + ... + ... + xn — 1.
21.10. Мы приходим к неравенству
21.11. Наиболее удобной является группировка
После того как мы применим формулу бинома и к (1 + x?)k, получим, что в общем члене содержится x100 ? (5k ? 2m). Остается выяснить, принимает ли 5k ? 2m все значения от 0 до 100, и если не все, то сколько значений окажутся пропущенными. Следует иметь в виду, что m, k = 0, 1, ..., 20, но m ? k.
21.12. Для получения рекуррентной формулы достаточно разобрать два случая: а) в первой группе один элемент (а1); б) в первой группе два элемента (а1, а2).
21.13. Чтобы получить рекуррентную формулу, связывающую Mn и Mn + 1, где через Mn обозначен ответ задачи, нужно найти число точек пересечения (n + 1)-й прямой со всеми остальными. Как с этим числом связано количество вновь образовавшихся областей?
Рекуррентное соотношение будет иметь вид
Mn + 1 = Mn + m + n + 1