Сегодня ночь поедания мозгов и все зомби соберутся вместе, чтобы отведать немного деликатесных мозгов. Артистичная Хайди планирует пробраться на вечеринку, прикинувшись одним из зомби. Её целью является унести с собой хотя бы один мозг, чтобы потом проанализировать его дома и получить стратегическое преимущество.

Всего этой ночью на вечеринке будет n гостей: n - 1 настоящий зомби, и Хайди, прикидывающаяся зомби. Ожившие мертвецы любят иерархию также как они любят мозги: каждому из них присвоен уникальный ранг от 1 до n - 1, а Хайди, которая всё-таки несколько отличается от остальных, присвоен максимально возможный ранг n. На вечеринке будет сундук с мозгами и каждый из пришедших видит, сколько мозгов находится в сундуке. Далее мозги распределяются между всеми пришедшими по следующей процедуре:

Зомби с максимальным рангом выдвигает предложение, о том как следует разделить мозги, то есть сколько именно мозгов достанется каждому конкретно (мозг считается неделимой сущностью). Далее происходит голосование, если хотя бы половина присутствующих принимают предложение, мозги распределяются соответствующим образом и начинается пир. Однако, если большинство не достигается, тогда зомби с максимальным рангом убивают и следующие по иерархии зомби выдвигает своё предложение. Если его также убивают, тогда в дело вступает третий по рангу зомби и так далее. Обратите внимание, что для победы в голосовании достаточно хотя бы половины голосов — в случае равенства голос зомби с максимальным рангом (из ещё не убитых) считается дважды, и конечно он голосует за своё предложение, чтобы остаться в живых.

Как известно, зомби очень жадные и хитрые — и сами зомби это тоже прекрасно знают, поскольку мозги всех зомби похожи. Как следствие, зомби никогда не поддержит предложение, если оно является для него субоптимальным, то есть если предложение не является строго лучше, чем любое другое потенциальное предложение в дальнейшем, то зомби проголосует против него. И будьте осторожны, хотя обычно зомби выглядят достаточно глупыми, сегодня их мозги работают прекрасно. Приоритеты каждого зомби этой ночью выглядят так (в порядке убывания):

1. пережить вечеринку (они уже один раз умерли, и знают что это сомнительное удовольствие),
2. получить как можно больше мозгов.

Хайди ходит первой, и ей требуется выдвинуть предложение, с которым согласится как минимум половина присутствующих, и при этом самой Хайди достанется хотя бы один мозг.

Чему равно минимально возможное количество мозгов в сундуке, при котором желаемое Хайди становится возможным?