Комментарии, ответы и решения задания №9

Комментарии, ответы и решения задания №9

Задача 1. Какое наименьшее количество типов монет должен выпустить монетный двор России, чтобы любую сумму от 1 до 20 рублей можно уплатить не более чем двумя монетами (без сдачи)?

Ответ: 6 монет

Пример:  монеты достоинством в 1,3,5,7,9 и 10 рублей  удовлетворяют условию задачи:

(1, 2=1+1,3, 4=3+1,5,6=5+1, 7, 8=7+1, 9,10, 11=10+1,12=9+3,13 = 10+3,

14=9+5,15=10+5,16=9+7, 17=10+7,18=9+9,19=19+9,20=10+10).

Оценка: Покажем, что пяти монет не хватит. В самом деле, имея монеты пяти типов, мы сможем с соблюдением условия задачи уплатить не более 20 денежных сумм: не более десяти, беря по две различные монеты; пять, беря по две одинаковые монеты; и ещё пять, беря по одной монете. Поскольку требуется, чтобы мы могли уплатить ровно 20 различных сумм, все перечисленные выше суммы должны быть различными. Кроме того, поскольку все суммы, которые требуется уплатить, равны целому числу рублей (1,2,…10), каждая их наших монет должна быть достоинством в целое число рублей (ведь одна она тоже составляет одну их искомых сумм). Поэтому обязательно должна быть монета достоинством в 1 рубль. Тогда двухрублевой монеты нет (иначе сумму в 2 рубля можно было бы уплатить двумя различными способами), а трехрублевая обязательно есть, четырехрублевой нет (4=3+1), а пятирублевая есть. Получается, что сумму в 6 рублей можно составить двумя способами: 6=5+1=3+3. Значит, сделать все 20 сумм различными всё равно не удастся.

Задача 2. Натуральные числа 22,23 и 24 обладают тем свойством, что в разложении каждого из них на простые множители каждый множитель входит в нечетной степени: 22 = 21·111, 23 = 231,24 = 23· 31. Какое наибольшее количество последовательных натуральных чисел может обладать таким свойством?

Ответ: 7

Пример:  29,30,31,32,33,34,35.

Оценка: Покажем, что восьми подряд идущих чисел с указанным свойством быть не может.

Действительно, одно из этих чисел (обозначим его n) делится на 8. Среди восьми наших чисел обязательно будет либо число (n – 4), либо число (n + 4). Оно делится на 4, но не делится на 8, что противоречит условию, так как делитель 2 входит в это число в четной степени.

Задача 3. Имеется неограниченное число фишек шести цветов. Какое наименьшее число фишек нужно расположить в ряд, чтобы для любых двух различных цветов в ряду нашлись две соседние фишки этих цветов?

Ответ: 18 фишек

Пример:  123456246325164135 (цифрами обозначены цвета).

Оценка: Из условия следует, что для каждого фиксированного цвета А фишка этого цвета должна встретиться в паре с фишкой каждого из остальных 5 цветов. В ряду фишка имеет не более двух соседей, поэтому фишка цвета А должна встретиться не менее 3 раз. Аналогично с каждым другим цветом. Таким образом, всего должно быть не менее фишек.