Задание 23. Информатика. ЕГЭ. Поляков-7371

(Я. Малыгин) Требуемая сумма набирается разным количеством одно- трех- и пятирублевых монет. Например, пусть в сумме нет ни одной пятирублевой монеты. Количество таких вариантов будет определяться возможным количеством трехрублевых монет, которых может быть от \(0\) до \(112500 // 3\) (целочисленное деление на три), т.е. \(37501\) вариантов. Недостающий остаток суммы «добивается» рублевыми монетами. Например, если \(10~000\) трехрублевых монет, то остаток \(112500 - 3 \cdot 10000 = 82500.\) Если пятирублевая монета одна, то количество вариантов будет \((112500 - 1 \cdot 5) //3 +1.\) Т.е. общее число вариантов можно посчитать следующим алгоритмом (\(i\) — количество пятирублевых монет в наборе):

Python

n = 0
for i in range(112500//5+1): n+= (112500 - 5*i)//3 + 1
a = [int(x) for x in str(n)]
print(sum(a))

Ответ: \(37\)

Моё старое (неправильное) решение:

Заметим сначала, что \(112~500 / 5 = 22500\), а \(5\) рублей можно выдать тремя способами: \(5\), \(3 + 1 + 1\) и \(1 + 1 + 1 + 1 + 1\). Обозначим эти способы как \(A\), \(B\) и \(C\). Тогда возможный размен суммы Теодора представляет собой комбинацию из \(22500\) символов \(AA \ldots AB \ldots BC \ldots C\). Разделим эти символы двумя запятыми: \(AA \ldots A,B \ldots B,C \ldots C\). В такой записи будет ровно \(22502\) символа. И задача сводится к нахождению всевозможных расстановок двух запятых по \(22502\) позициям. Это число равно $$ C^2_{22502} = \frac{22502!}{2! \cdot 22500!} = \frac{22501 \cdot 22502}{2} $$

Комментарий Ярослава Малыгина на это решение:

Не согласен с вашим решением задачи в котором варианты жестко разделены буквами на группы по пять рублей. Переход между группами невозможен, что уменьшает общее число вариантов.

Пусть сумма равна не \(112500,\) а \(10.\) Тогда в соответствии с вашим решением количество вариантов будет \(\cfrac{4!}{2! \cdot 2!} = 6,\) которые можно перечислить, пользуясь вашими буквенными обозначениями, как \(AA,\) \(AB,\) \(AC,\) \(BB,\) \(BC,\) \(CC.\) Или по количеству пяти- трех и однорублевых монет:

пятирублевые	трехрублевые	однорублевые	буквенное обозначение
0	0	10	\(CC\)
0	1	7	\(BC\)
0	2	4	\(BB\)
0	3	1	такого варианта в вашем решении не предусмотрено
1	0	5	\(AC\)
1	1	2	\(AB\)
2	0	0	\(AA\)