12 гномов нашли клад из 99 золотых монет.Долго спорили как разделить находку и никак на могли прийти к единому решению.Наступила ночь,гномы расселись вокруг костра и доверили это сложное дело самому мудрому из них гному Умнику.Умник должен предложить,сколько монет взять себе и сколько дать каждому(необязательно одинаковое количество каждому,0 монет тоже можно давать).Затем 11 гномов проголосуют за предложение Умника.Каждый из гномов жаден и проголосует <за>,только если он получит больше монет,чем каждый из двух его соседей,иначе он проголосует <против>,если большинство проголосует <за>, по предложение Умника принимается.В противном случае Умник не получает ничего,и гномы делят монеты далее без него.Какое наибольшее количество монет может получить Умник?

Question 1

Задача Задача №46539

А

Аноним

15 ноября 2023 14:09 · публичный вопрос

А

Аноним 15 ноября 2023 14:09

12 гномов нашли клад из 99 золотых монет.Долго спорили как разделить находку и никак на могли прийти к единому решению.Наступила ночь,гномы расселись вокруг костра и доверили это сложное дело самому мудрому из них гному Умнику.Умник должен предложить,сколько монет взять себе и сколько дать каждому(необязательно одинаковое количество каждому,0 монет тоже можно давать).Затем 11 гномов проголосуют за предложение Умника.Каждый из гномов жаден и проголосует <за>,только если он получит больше монет,чем каждый из двух его соседей,иначе он проголосует <против>,если большинство проголосует <за>, по предложение Умника принимается.В противном случае Умник не получает ничего,и гномы делят монеты далее без него.Какое наибольшее количество монет может получить Умник?

Answer

Это известная задача, в которой можно использовать стратегию "разделяй и властвуй". Гном Умник должен предложить такой вариант распределения денег, при котором у него будет поддержка большинства гномов. Поскольку гномы жадные, и каждый хочет получить больше монет, чем его соседи, Умник может использовать эту черту для своей стратегии.

Важно обеспечить поддержку как минимум 6 из 11 гномов, чтобы добиться большинства голосов. Умник может решить это, давая одинаковое количество монет гномам, которых он хочет обеспечить поддержкой, и давая 0 монет гномам, которым не обязательно предлагать монеты, чтобы гарантировать большинство голосов.

Пример стратегии:

Умник решает дать монеты только тем гномам, которые находятся через одного от него. То есть даем монеты 1-му, 3-му, 5-му и так далее гномам по кругу.

Схема распределения будет выглядеть так:

Гном 1 (сосед Умника): 0 монет
Гном 2: 1 монета (голос "за", т.к. получает больше, чем оба его соседа)
Гном 3: 0 монет
Гном 4: 1 монета (голос "за")
Гном 5: 0 монет
Гном 6: 1 монета (голос "за")
Гном 7: 0 монет
Гном 8: 1 монета (голос "за")
Гном 9: 0 монет
Гном 10: 1 монета (голос "за")
Гном 11: 0 монет
Гном 12 (Умник): оставшееся количество монет

Здесь Умник даёт по 1 монете гномам 2, 4, 6, 8 и 10 (всего 5 монет), и они проголосуют "за", так как получают больше, чем их соседи. Остальные не получают ничего и будут голосовать "против". Но Умник уже обеспечил себе большинство голосов. Таким образом, Умник забирает оставшиеся 99 - 5 = 94 монеты.

Question 2

12 гномов нашли клад из 99 золотых монет.Долго спорили как разделить находку и никак на могли прийти к единому решению.Наступила ночь,гномы расселись вокруг костра и доверили это сложное дело самому мудрому из них гному Умнику.Умник должен предложить,сколько монет взять себе и сколько дать каждому(необязательно одинаковое количество каждому,0 монет тоже можно давать).Затем 11 гномов проголосуют за предложение Умника.Каждый из гномов жаден и проголосует <за>,только если он получит больше монет,чем каждый из двух его соседей,иначе он проголосует <против>,если большинство проголосует <за>, по предложение Умника принимается.В противном случае Умник не получает ничего,и гномы делят монеты далее без него.Какое наибольшее количество монет может получить Умник?

Answer

Это известная задача, в которой можно использовать стратегию "разделяй и властвуй". Гном Умник должен предложить такой вариант распределения денег, при котором у него будет поддержка большинства гномов. Поскольку гномы жадные, и каждый хочет получить больше монет, чем его соседи, Умник может использовать эту черту для своей стратегии. Важно обеспечить поддержку как минимум 6 из 11 гномов, чтобы добиться большинства голосов. Умник может решить это, давая одинаковое количество монет гномам, которых он хочет обеспечить поддержкой, и давая 0 монет гномам, которым не обязательно предлагать монеты, чтобы гарантировать большинство голосов. Пример стратегии: Умник решает дать монеты только тем гномам, которые находятся через одного от него. То есть даем монеты 1-му, 3-му, 5-му и так далее гномам по кругу. Схема распределения будет выглядеть так: - Гном 1 (сосед Умника): 0 монет - Гном 2: 1 монета (голос "за", т.к. получает больше, чем оба его соседа) - Гном 3: 0 монет - Гном 4: 1 монета (голос "за") - Гном 5: 0 монет - Гном 6: 1 монета (голос "за") - Гном 7: 0 монет - Гном 8: 1 монета (голос "за") - Гном 9: 0 монет - Гном 10: 1 монета (голос "за") - Гном 11: 0 монет - Гном 12 (Умник): оставшееся количество монет Здесь Умник даёт по 1 монете гномам 2, 4, 6, 8 и 10 (всего 5 монет), и они проголосуют "за", так как получают больше, чем их соседи. Остальные не получают ничего и будут голосовать "против". Но Умник уже обеспечил себе большинство голосов. Таким образом, Умник забирает оставшиеся 99 - 5 = 94 монеты.