Задача 19. Пираты и монеты

Пираты нашли сундук с сокровищами, в котором было 60 монет достоинством 1 дукат и 60 монет достоинством 5 дукатов.
а) Получится ли поделить все деньги поровну между 18 пиратами (каждому должно достаться целое число монет, сдачи и размена ни у кого из пиратов нет)?
б) Получится ли поделить все деньги поровну между 40 пиратами (каждому должно достаться целое число монет, сдачи и размена ни у кого из пиратов нет)?
в) При каком наибольшем количестве пиратов капитану всегда удастся поделить монеты между ними, каким бы способом ему ни захотелось это сделать (возможно, кому-то из пиратов будет полагаться 0 монет)?

Решение

а) Общая сумма денег: 5\cdot60+1\cdot60=360 (дукатов)
360:18=20 (дукатов) — столько надо дать каждому пирату
Это можно сделать так:
4 монеты \cdot 5 дукатов = 20 дукатов — отдать 15 пиратам
20 монет \cdot 1 дукат = 20 дукатов — отдать 3 пиратам
Ответ: да

 

б) 360:40=9 (дукатов) — столько надо дать каждому пирату
Способы выдать 9 дукатов:
1) 9 монет \cdot 1 дукат
2) 1 монета \cdot 5 дукатов + 4 монеты \cdot 1 дукат
Монеты в 5 дукатов необходимо раздать все, поэтому способ №2 необходимо обязательно использовать 
40 пиратов получат по 1 монете в 5 дукатов, останется 20 монет по 5 дукатов, их отдать некому, т.к. иначе сумма у пирата превысит 9 дукатов.
Ответ: нет

 

в) Любую сумму S (S\leq304) можно выдать одному пирату следующим образом.
Разделим S на 5 с остатком:

    \[S=5k+r, \;\;\;r\in\{0;1;2;3;4\}\]


Выдадим k монет по 5 дукатов и r монет по 1 дукату.
Если S>304, то выдаем 60 монет по 5 дукатов и (S-300) монет по 1 дукату.

Пусть n пиратов, каждый получил сумму S_i, \;i=1,...,n
В самом плохом случае

    \[S_i=5k_i+4,\;i=1,...,n\]


Так как монет в 1 дукат всего 60, то суммы с остатком 4 при делении на 5 можно выдать только 15 пиратам.
Значит в самом плохом случае 15 пиратов могут получить суммы S_i=5k_i+4, а пират №16 — оставшиеся деньги (возможно 0).

Если пиратов n\geq17, то нельзя любым способом поделить монеты между ними. Например, нельзя 16-ти пиратам выдать по 4 дуката (нужно 64 монеты по 1 дукату, таких монет всего 60), а между оставшимися пиратами любым способом поделить 296 дукатов.

Пусть пиратов n=16 и капитан хочет поделить деньги между ними так:

    \[S_1,S_2,S_3,...,S_{16}\]


Можно считать, что эта последовательность не возрастающая:

    \[S_{1}\geq\,S_{2}\geq\,S_{3}\geq...\geq\,S_{16}\]

Будем выдавать монеты, начиная с наибольшей суммы, используя максимальное число монет по 5 дукатов.

Если S_{1}\leq304, то первому пирату выдадим k_1 монет по 5 дукатов и r_1 монет по 1 дукату, где S_1=5k_1+r_1,\;0\leq\,r_1\,\leq4.
Если S_1>304, то первому пирату выдадим все 60 монет по 5 дукатов и (S_{1}-300) монет по 1 дукату.
Аналогично можно выдать суммы S_2,...,S_{15}. Пират №16 получает просто остаток: S_{16}=360-S_1-S_2-...-S_{15}.

Другими словами, i-му пирату сначала выдаем максимальное число монет по 5 дукатов. Если после этого монеты по 5 дукатов остаются, от он получит не более 4-х монет по 1 дукату. Если он получает последние монеты по 5 дукатов, то оставшуюся сумму он получает монетами по 1 дукату. Суммы S_{i+1},...,S_{16} при этом очевидно выдаются монетами по 1 дукату или равны 0.

Ответ: 16

Комментарии 1

  • Предлагаю более корректное условие Пункта «В»: При каком наибольшем количестве пиратов капитану всегда удастся поделить дукаты поровну между ними, каким бы способом ему ни захотелось это сделать (от 1 до максимально возможного количества дукатов каждому)? Возможно, при каком-то способе ему самому достанется 0 дукатов. Капитана в ответе — тоже учитывать.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.