РЕШУ ОЛИМП — математика

Задания

В комплекте для сборки игрушечного поезда есть один локомотив, который всегда расположен спереди 2n одинаковых красных вагонов и 3n одинаковых желтых вагонов. Назовем поезд длинным, если в нем есть хотя бы n вагонов, не считая локомотива. Сколько различных длинных поездов можно собрать, используя этот комплект? Ответ должен быть дан в замкнутом виде: в ответе не должно быть сумм с переменным числом слагаемых, многоточий и так далее.

Решение. Посчитаем количество всех поездов, которые можно собрать в данном наборе. Зафиксируем число k $левая круглая скобка 0 меньше или равно k меньше или равно 2n правая круглая скобка$ и посчитаем, сколько всего поездов с ровно k красными вагонами. Желтых вагонов может быть от 0 до 3n, и для каждого числа l желтых вагонов от 0 до 3n мы выбираем k мест в строке длины k + l. Таким образом, искомое количество поездов с k красными вагонами равно сумме

$\binomkk плюс \binomk плюс 1k плюс \ldots плюс \binomk плюс 3nk.$

Докажем, что эта сумма равна $\binomk плюс 3n плюс 1k плюс 1.$ Распишем каждое слагаемое, пользуясь следующим тождеством Паскаля:

$\binomab = \binoma плюс 1b плюс 1 минус \binomab плюс 1.$

Мы получим:

$левая круглая скобка \binomk плюс 1k плюс 1 минус \binomkk плюс 1 правая круглая скобка плюс левая круглая скобка \binomk плюс 2k плюс 1 минус \binomk плюс 1k плюс 1 правая круглая скобка плюс левая круглая скобка \binomk плюс 3k плюс 1 минус \binomk плюс 2k плюс 1 правая круглая скобка плюс$
$плюс \ldots плюс левая круглая скобка \binomk плюс 3nk плюс 1 минус \binomk плюс 3n минус 1k плюс 1 правая круглая скобка плюс левая круглая скобка \binomk плюс 3n плюс 1k плюс 1 минус \binomk плюс 3nk плюс 1 правая круглая скобка .$ $левая круглая скобка \binomk плюс 1k плюс 1 минус \binomkk плюс 1 правая круглая скобка плюс левая круглая скобка \binomk плюс 2k плюс 1 минус \binomk плюс 1k плюс 1 правая круглая скобка плюс$
$плюс левая круглая скобка \binomk плюс 3k плюс 1 минус \binomk плюс 2k плюс 1 правая круглая скобка плюс \ldots плюс$
$плюс левая круглая скобка \binomk плюс 3nk плюс 1 минус \binomk плюс 3n минус 1k плюс 1 правая круглая скобка плюс левая круглая скобка \binomk плюс 3n плюс 1k плюс 1 минус \binomk плюс 3nk плюс 1 правая круглая скобка .$ $левая круглая скобка \binomk плюс 1k плюс 1 минус \binomkk плюс 1 правая круглая скобка плюс левая круглая скобка \binomk плюс 2k плюс 1 минус \binomk плюс 1k плюс 1 правая круглая скобка плюс$
$плюс левая круглая скобка \binomk плюс 3k плюс 1 минус \binomk плюс 2k плюс 1 правая круглая скобка плюс$
$плюс \ldots плюс левая круглая скобка \binomk плюс 3nk плюс 1 минус \binomk плюс 3n минус 1k плюс 1 правая круглая скобка плюс$
$плюс левая круглая скобка \binomk плюс 3n плюс 1k плюс 1 минус \binomk плюс 3nk плюс 1 правая круглая скобка .$

Здесь разложены и выписаны явно первые три и последние два члена вычисляемой суммы. В каждой скобке вычитаемое равно уменьшаемому из предыдущей скобки. Нетронутым останется лишь уменьшаемое в последней скобке, равное $\binomk плюс 3n плюс 1k плюс 1,$   — это и есть искомый результат сложения. Заметим, что этот результат равен $\binomk плюс 3n плюс 13n$ в силу симметрии биномиальных коэффициентов. Теперь нужно сложить эти числа по всем k от 0 до 2n. Получим сумму

$\binom3n плюс 13n плюс \binom3n плюс 23n плюс \ldots плюс \binom5n плюс 13n,$

которая суммируется аналогичным образом, и результат этого суммирования равен

$\binom5n плюс 23n плюс 1 минус \binom3n3n = \binom5n плюс 22n плюс 1 минус 1.$

Мы посчитали количество всех поездов. Осталось лишь вычесть количество поездов, в которых не более $n минус 1$ вагонов, но для каждого $l меньше или равно n минус 1$ количество поездов длины l очевидно равно  $2 в степени l ,$ а всего в сумме таких поездов  $2 в степени n минус 1.$ Таким образом, длинных поездов $\binom5n плюс 22n плюс 1 минус 2 в степени n .$

Ответ: $\binom5n плюс 22n плюс 1 минус 2 в степени n .$

Содержание критерия	Оценка	Балл
Верное решение	+	15
Арифметическая ошибка в вычислениях	+.	13
Посчитано количество всех поездов, в том числе с ⩽n−1 вагонами	±	10
Верный ход решения, но суммы биноминальных коэффициентов не вычислены в замкнутом виде	∓	6
Посчитан один из трех различных вариантов	−.	3
Решение не соответствует ни одному из критериев выше	−	0

№ п/п	№ задания	Ответ
1	11628	$\binom5n плюс 22n плюс 1 минус 2 в степени n .$

Ключ