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

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

Так как гномы голосуют за предложение только в том случае, если они получают больше монет, чем каждый из их соседей, Умник может использовать следующую стратегию: он меняет количество монет, которые получат гномы, таким образом, чтобы одна группа гномов получила больше другой — и именно эта группа проголосует за него. Для упрощения расчётов мы можем предположить, что гномы расположены зигзагом в плане количества монет (например, первому гному 1 монета, второму — 2, третьему — 1, четвёртому — 2, и так далее). Эта схема обеспечит большинство голосов, поскольку каждый гном с большим числом монет будет окружён двумя с меньшим числом.

Если Умник отдаст по одной монете гномам, получающим меньшее количество, и по две монеты тем, кто получает больше, он затратит:

(6 гномов × 1 монета) + (5 гномов × 2 монеты) = 6 + 10 = 16 монет.

Оставшиеся будут для Умника:

99 монет - 16 монет = 83 монеты.

Таким образом, Умник может получить наибольшее количество монет — 83, делегируя оставшиеся 16 монет таким образом, чтобы завоевать большинство голосов других гномов.