Есть 16 монет по 2 рубля и 29 монет по 5 рублей. а) Можно ли этими монетами набрать сумму 175 рублей? б) Можно ли этими монетами набрать сумму 176 рублей? в) Какое наименьшее количество монет, каждая по 1 рублю, нужно добавить, чтобы иметь возможность набрать любую целую сумму от 1 рубля до 180 рублей включительно?

а) Представим сумму 175 рублей как 5x + 2y, где x — количество монет по 5 рублей, y — по 2 рубля, 0 x 29, 0 y 16. Подбираем: при x = 29 (нечётно е) получаем 5* 29 = 145, тогда 2y = 175 - 145 = 30, откуда y = 15 16. Комбинация существует. б) Для суммы 176 рублей: 5x + 2y = 176, x должно быть чётным. Максимальное чётное x = 28 даёт 5* 28 = 140, тогда y = (176 - 140)/2 = 18 > 16. При уменьшении x значение y увеличивается, других целых решений в пределах ограничений нет. Сумму 176 рублей набрать нельзя. в) Пусть A — множество сумм, набираемых монетами 2 и 5 рублей: A = 2b + 5c 0 b 16,0 c 29. Максимальная сумма в A равна 16* 2 + 29* 5 = 177. Проверка показывает, что все целые числа от 4 до 173 принадлежат A, а числа 174 и 176 не принадлежат. Таким образом, A = 0; 2U 4; 5; ; 173U 175; 177. Чтобы с добавлением k монет по 1 рублю можно было набрать любую сумму от 1 до 180, необходимо и достаточно, чтобы для каждого Sin [1; 180] существовало tin A такое, что 0 S - t k. Это условие равносильно тому, что максимальный разрыв между последовательными элементами A (и от 0 до первого, и от последнего до 180) не превышает k. Разрывы: между 0 и 2 — число 1 (длина 1); между 2 и 4 — число 3 (длина 1); между 173 и 175 — число 174 (длина 1); между 175 и 177 — число 176 (длина 1); после 177 до 180 — числа 178, 179, 180 (длина 3). Наибольшая длина разрыва равна 3, следовательно, минимальное k = 3. Ответ: а) Можно набрать сумму 175 рублей. б) Нельзя набрать сумму 176 рублей. в) 3.

а) да б) нет в) 3