12 гномов нашли клад из 99 золотых монет.Долго спорили как разделить находку и никак на могли прийти к единому решению.Наступила ночь,гномы расселись вокруг костра и доверили это…
12 гномов нашли клад из 99 золотых монет.Долго спорили как разделить находку и никак на могли прийти к единому решению.Наступила ночь,гномы расселись вокруг костра и доверили это сложное дело самому мудрому из них гному Умнику.Умник должен предложить,сколько монет взять себе и сколько дать каждому(необязательно одинаковое количество каждому,0 монет тоже можно давать).Затем 11 гномов проголосуют за предложение Умника.Каждый из гномов жаден и проголосует <за>,только если он получит больше монет,чем каждый из двух его соседей,иначе он проголосует <против>,если большинство проголосует <за>, по предложение Умника принимается.В противном случае Умник не получает ничего,и гномы делят монеты далее без него.Какое наибольшее количество монет может получить Умник?
Чтобы решить эту задачу, мы должны убедиться, что большинство гномов (то есть, как минимум 6 из 11) голосуют за предложение Умника. Гномы голосуют за предложение только в том случае, если они получают больше монет, чем каждый из двух их соседей. Это означает, что мы должны устроить монеты таким образом, чтобы чередоваться количества монет между гномами так, чтобы каждый второй гном получал больше своих соседей.
Чтобы это работало, Умник может начать раздавать монеты следующим образом: первому гному 1 монету, следующему 2, следующему снова 1, следующему 2 и так далее, чередуя, пока он не закончит распределение монет среди 11 гномов. Таким способом гномы получат монеты в следующем порядке: 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1. Суммируя количество монет для четных позиций (то есть те, кто получают больше), мы получаем: 2 + 2 + 2 + 2 + 2 = 10 монет.
Таким образом, 6 гномов с количеством монет 2 будут голосовать "за", а 5 гномов с количеством монет 1 будут голосовать "против", так как они получают меньше своих соседей. В такой раскладке гарантировано большинство голосов "за".
Теперь рассчитаем, сколько монет останется Умнику. Сначала вычтем количество монет, которое было распределено между другими гномами:
99 монет (всего) - 10 монет (разданы голосующим "за") - 5 монет (разданы голосующим "против") = 99 - 15 = 84 монеты.
Таким образом, Умник может забрать себе оставшиеся 84 монеты.
