Решение задачи 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), которая дает такой же остаток и добавляем нужное число пятерок.