Задача 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

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

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

  • И всё-таки пункт в) убивает. Ответ: 16 пиратов может быть самое большее, если мы делим монеты (или деньги даже) ЛЮБЫМ способом, как вы подчёркиваете. Верно? Абсолютно ЛЮБЫМ! Ок. Вот капитан захотел поделить монеты между 16 пиратами поровну. Монет всего 60+60=120, 120/16=7,5 монет каждому. Попробуем деньги поделить поровну в этом случае: денег всего 60*1+60*5=360 дукат. Далее 360/16=22,5 дуката каждому пирату. Таким образом, если пиратов 16, то поровну распределить между ними нельзя ни монеты ни деньги, следовательно способ распределения «поровну» не учтён, а значит способ распределения монет или денег между пиратами уже не любой.

    • Мне тоже не нравится формулировка задачи, она вызывает много вопросов. Адекватное решение возможно, если подразумевать любой доступный (реализуемый) способ.

  • Оговорка про «кому-то 0 монет» делает задачу бессмысленной: делим 120 монет как захотим, а всем, кому не хватило, раздаём по 0 монет!

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

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

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