|
|
 |
Условие
Тридцать три богатыря нанялись охранять Лукоморье за 240 монет. Хитрый дядька Черномор может разделить богатырей на отряды произвольной численности (или записать всех в один отряд), а затем распределить всё жалованье между отрядами.
Каждый отряд делит свои монеты поровну, а остаток отдаёт Черномору. Какое наибольшее количество монет может достаться Черномору, если:
а) жалованье между отрядами Черномор распределяет как ему угодно;
б) жалованье между отрядами Черномор распределяет поровну?
Решение
С отряда в N богатырей Черномор получит в лучшем случае N – 1 монету, так как остаток меньше делителя. Значит, всего он получит не более чем
33 – K монет, где K – число отрядов. Но если отряд всего один, то, поскольку 240 = 33·7 + 9, Черномору достанется лишь 9 монет. Значит, 32 монеты Черномору получить не удастся.
а) Покажем, как получить 31 монету. Например, Черномор делит богатырей на два отряда: в первом – 32 богатыря, а во втором – всего один. Он может дать первому отряду 63 монеты (из которых получит 31), а остальные 177 монет отдать единственному богатырю из второго отряда.
б) Чтобы получить 31 монету, Черномор должен разделить богатырей на два отряда и выдать каждому отряду по 120 монет. При этом с отряда в N человек он должен получить N – 1 монету. Это значит, что 121 должно делиться на N. Однако 121 делится только на 1, 11 и 121, а из двух таких чисел невозможно сложить 33. Поэтому 31 монету Черномору получить не удастся.
А вот получить 30 монет можно. Образуем, например, один отряда из 27 богатырей и два отряда по 3 богатыря. Каждый отряд получает по 80 монет, и, поскольку 81 делится на численность каждого отряда, "откат" составит 26 + 2 + 2 = 30 монет.
Ответ
а) 31 монета; б) 30 монет.
