Информатика. ЕГЭ
Задание 23. Информатика. ЕГЭ. Поляков-7371
- Просмотры: 1324
- Изменено: 7 мая 2025
(А. Игнатюк) Теодор пришел в магазин, чтобы разменять сумму в \(112~500\) рублей монетами в \(1\), \(3\) и \(5\) рублей. Определите, сколько у Теодора существует способов сделать это. В ответ запишите сумму цифр полученного числа.
Решение:
(Я. Малыгин) Требуемая сумма набирается разным количеством одно- трех- и пятирублевых монет. Например, пусть в сумме нет ни одной пятирублевой монеты. Количество таких вариантов будет определяться возможным количеством трехрублевых монет, которых может быть от \(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\) |
Новый тренажёр-эмулятор
Станции КЕГЭ
Эффективно готовьтесь к ЕГЭ по информатике с новым тренажёром, эмулирующем работу станции КЕГЭ, которая используется на реальном экзамене
Новое видео
Поддержать автора сайта!
Расписание пробников Статграда в 2026/27 учебном году
Информатика ОГЭ 9 класс
- 13 октября 2026 года
- 3 декабря 2026 года
- 21 января 2027 года
- 19 февраля 2027 года
- 23 марта 2027 года
- 27 апреля 2027 года
Математика ОГЭ 9 класс
- 23 сентября 2026 года
- 1 декабря 2026 года
- 22 января 2027 года
- 3 марта 2027 года
- 14 апреля 2027 года
Физика ОГЭ 9 класс
- 19 октября 2026 года
- 10 декабря 2026 года
- 29 января 2027 года
- 17 марта 2027 года
- 22 апреля 2027 года
Математика ЕГЭ 10 класс
- 3 февраля 2027 года
- 11 мая 2027 года
Информатика ЕГЭ 11 класс
- 22 октября 2026 года
- 15 декабря 2026 года
- 26 января 2027 года
- 2 марта 2027 года
- 13 апреля 2027 года
Математика ЕГЭ 11 класс
- 30 сентября 2026 года
- 17 декабря 2026 года
- 9 февраля 2027 года
- 16 марта 2027 года
- 21 апреля 2027 года
Физика ЕГЭ 11 класс
- 14 октября 2026 года
- 16 декабря 2026 года
- 4 февраля 2027 года
- 12 марта 2027 года
- 9 апреля 2027 года