12 гномов нашли клад из 99 золотых монет.Долго спорили как разделить находку и никак на могли прийти к единому решению.Наступила ночь,гномы расселись вокруг костра и доверили это сложное дело самому мудрому из них гному Умнику.Умник должен предложить,сколько монет взять себе и сколько дать каждому(необязательно одинаковое количество каждому,0 монет тоже можно давать).Затем 11 гномов проголосуют за предложение Умника.Каждый из гномов жаден и проголосует <за>,только если он получит больше монет,чем каждый из двух его соседей,иначе он проголосует <против>,если большинство проголосует <за>, по предложение Умника принимается.В противном случае Умник не получает ничего,и гномы делят монеты далее без него.Какое наибольшее количество монет может получить Умник?
Чтобы убедиться в том, что Умник получит наибольшее количество монет, ему необходимо устроить так, чтобы большинство гномов были довольны предложением, то есть хотя бы 6 из 11 гномов должны проголосовать за него. Умник должен использовать их жадность в свою пользу, так чтобы налаживать сложные отношения соседства и убедить хотя бы часть гномов принять его предложение.
Умник может придумать систему, при которой голосование гарантированно выйдет в его пользу. Он может предложить следующий план:
- Он сам берет наибольшее возможное количество монет, скажем X.
- Два его соседа не получают ничего (0 монет).
- Следующие за ними два гнома – по 1 монете каждый.
- Два следующих после них гнома – снова 0 монет.
- Следующие два гнома – опять по 1 монете.
- Затем ещё два гнома – 0 монет.
- Последние два, которые остались, – по 1 монете каждый.
Таким образом, Умник создаст паттерн, где гномы, получающие хоть что-то (1 монету), будут окружены соседями, у которых либо нет монет, либо такое же количество. Они проголосуют "За", так как получают больше своих соседей, у которых 0 монет. Таких гномов будет ровно 6, что является большинством, необходимым для принятия предложения.
Таким образом, если гномы сидят в кругу, мы можем распределить монеты следующим образом (начиная с Умника и идущим по часовой стрелке): X, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1.
Теперь нам нужно вычислить максимальное значение X. Мы распределили 6 монет по 1 каждому "за"-голосующему гному, так что:
99 монет – 6 монет = 93 монеты
Это максимальное количество монет, которое Умник может взять для себя и при этом гарантировать большинство голосов. Таким образом, Умник может получить 93 монеты.
