Решение задачи 431
Условие:
Лист бумаги можно разрезать на 6 или 12 частей. Каждый новый кусок можно разрезать на 6 или 12 частей или оставить целым и так далее. а) Можно ли таким образом разрезать лист на 40 частей? б) Докажите, что таким образом можно получить любое число частей, большее 40.
Решение:
Изначально имеется один кусок. Заметим, что при разрезе на 6 кусков число всех кусков увеличивается на 5, а при разрезе на 12 -- на 11. Задача сводится к следующей: имеется много монет достоинством 5 и 11, в пункте а) надо доказать, что нельзя выплатить 39, в пункте б) -- что можно выплатить любую сумму начиная с 40.
а) Рассмотрим все возможные варианты количества монет достоинством 11. Их количество варьируется от 0 до 3. Если их 0, 1, 2, 3, то надо пятерками выплатить 39, 28, 17, 6 соответственно. Осталось заметить, что числа 39, 28, 17 и 6 не кратны пяти.
б) Покажем, как выплатить все от 40 до 44:
40 = 5+5+5+5+5+5+5+5
41 = 11+5+5+5+5+5+5
42 = 11+11+5+5+5+5
43 = 11+11+11+5+5
44 = 11+11+11+11
Пусть надо выплатить сумму в N. N дает какой-то остаток при делении на 5. Берем сумму (40, 41, 42, 43 или 44), которая дает такой же остаток и добавляем нужное число пятерок.