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

Просмотры: 11
Изменено: 7 сентября 2024

(А. Игнатюк) Теодор пришел в магазин, чтобы разменять сумму в \(112~500\) рублей монетами в \(1\), \(3\) и \(5\) рублей. Определите, сколько у Теодора существует способов сделать это. В ответ запишите сумму цифр полученного числа.

Решение:

Заметим сначала, что \(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} $$

Python


n = 22501 * 22502 // 2
a = [int(x) for x in str(n)]
print(sum(a))

Ответ: \(37\)