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

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

Чтобы добиться этого, Умник может решить поступить следующим образом: он будет давать 1 монету каждому из 5 гномов, чередуя их с 6 гномами, которым не дает ничего. Таким образом, эти 5 гномов, получившие по монете, будут иметь больше, чем оба их соседа, которые получили 0 монет, и поэтому проголосуют "за".

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

Получается, что распределение будет выглядеть так:

• Крайнему гному слева от пятерки - 0 монет
• Крайнему гному справа от пятерки - 0 монет
• Пятерке гномов в середине - по 1 монете каждому, и по 2 монеты крайним
• Оставшимся 4 гномам - по 0 монет каждому

Итак, распределение монет выглядит так: 0, 2, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0.

Таким образом, Умник может взять оставшиеся монеты:

99 - (2 + 1 + 1 + 1 + 1 + 2) = 99 - 8 = 91 монету.

Умник, будучи самым мудрым среди гномов, получит 91 золотую монету и обеспечит поддержку большинства голосующих гномов.