19.03 Задачи формата ЕГЭ

a) Каждый пират должен получить количество дукатов, равное

Выдадим 15 пиратам по 4 монеты достоинством 5 дукатов, троим — по 20 монет достоинством 1 дукат.

б) Каждый пират должен получить количество дукатов, равное

Тогда нужно будет выдать каждому не менее 4 монет достоинством 1 дукат. Значит, всего монет достоинством 1 дукат нужно не менее 160 штук, а в сундуке их только 60. Следовательно, без сдачи и размена поделить все монеты поровну не получится.

в) Рассмотрим случай, когда пиратов 17 или больше. Приведём пример раздела, который капитан не сможет реализовать.

Пусть капитан хочет достичь следующего раздела: 16 пиратов должны получить по 4 дуката, один — все оставшиеся деньги, остальные, если они есть, — ничего. Тогда распределить монеты нельзя по тем же причинам, что и в пункте б).

Пусть пиратов 16. Покажем, как реализовать произвольный раздел. Заметим, что если некоторый раздел можно осуществить с помощью монет по 5 дукатов, то его можно осуществить и с помощью монет по 5 и по 1 дукату (при том, что сумма денег одна и та же), просто формируя пятерки из единиц.

Пусть некоторому пирату полагается дукатов. Выдадим ему количество дукатов, равное остатку числа по модулю 5, монетами по 1 дукату. Произведем эту операцию с каждым пиратом.

Сумма таких остатков для всех пиратов должна быть кратна 5, так как общая сумма денег кратна 5. Также эта сумма не больше чем так как каждому пирату придется выдать не более 4 монет по одному дукату, ведь остаток числа при делении на 5 не превышает 4. Наибольшее натуральное число, не превышающее 64 и кратное 5, равно 60. Значит, для описанной процедуры точно хватит монет по 1 дукату.

После вышеописанного каждому пирату недовыдано некоторое количество монет, кратное 5. Тогда очевидно, что оставшиеся монеты можно распределить нужным образом.