Задача про пять Элвисов и ограбление банка

Для удобства назовём грабителей Алексей, Борис, Владимир, Геннадий и Дмитрий. Алексей самый старший, Дмитрий — самый младший.

Проще всего решить эту задачу с конца, то есть представить, что осталось двое: Геннадий и Дмитрий. Это будет 4-й раунд голосования. Мы начнём с него и пройдём до самого первого предложения от старшего грабителя.

4-й раунд голосования, 2 грабителя. Геннадий предлагает забрать все деньги себе, то есть 100 мешков денег ему и 0 — Дмитрию:

100 — 0

Геннадию неважно, как проголосует Дмитрий: ему достаточно своего голоса, потому что тогда он получает 50%, а это означает победу.

Но теперь вспомним, что все грабители умные. Значит, предыдущий по старшинству грабитель Владимир должен был предвидеть такое развитие событий. Подумаем, какое предложение он мог бы сделать.

3-й раунд голосования, 3 грабителя. Владимиру нужен ещё один голос для победы. Он решит получить голос Дмитрия, потому что, если Владимир проиграет, останутся двое грабителей и все деньги заберёт Геннадий. 

Геннадию в любом случае невыгодно голосовать за предложение Владимира: ему выгоднее остаться вдвоём и получить всё.

Поэтому Владимир предложит Дмитрию 1 мешок денег, а Геннадию — 0:

99 — 0 — 1

2-й раунд голосования, 4 грабителя. Поднимаемся на уровень выше.

Борис понимает, что будет, если останутся 3 грабителя и кому это выгодно. Ему тоже нужен ещё один голос, чтобы набрать 50%. 

Ситуация с 3 грабителями невыгодна Геннадию, потому Борис предложит ему 1 мешок денег, а Владимиру и Дмитрию — ничего:

99 — 0 — 1 — 0

1-й раунд голосования, 5 грабителей. Доходим до предложения самого старшего, Алексея. 

Ему нужно два голоса. Он знает, кто проиграет в ситуации с 4 грабителями: Владимир и Дмитрий. Поэтому он предлагает им по 1 мешку денег, чтобы они проголосовали за него. Получается такое итоговое решение:

98 — 0 — 1 — 0 — 1

Результат:

Мы напишем небольшую программу на Python, которая будет принимать любое количество грабителей и денег.

От программы в качестве ответа нужен список: пронумерованное количество элементов, которое будет соответствовать номерам грабителей. То есть для 5 грабителей и 100 мешков денег мы должны получить [98, 0, 1, 0, 1].

Нам понадобится функция, которая принимает на вход количество грабителей и мешков денег.

def elvises_division(n, bags=100):

Теперь начинаем с конца — если остался один грабитель, он получает всё:

# если остался один Элвис — он забирает всё
if n == 1:
return [bags]

В логическом решении в конце остаются 2 грабителя, но в программировании лучше добавить точности.

Если грабителей больше, то функция идёт дальше. Следующей строкой кода уменьшаем количество грабителей на 1 и снова пытаемся вызвать эту же функцию — это называется рекурсия:

# предыдущий результат для n-1 грабителей
prev = elvises_division(n – 1, bags)

Составляем пустой список из количества грабителей, чтобы учесть, кто сколько получил:

# пустой список распределения мешков
result = [0] * n

Теперь добавим проверку нужного количества голосов:

# проверка нужного количества голосов
votes_needed = (n // 2) + (n % 2)

Тут есть нюанс: один из голосов — это голос самого старшего грабителя, который всегда голосует за свой план. Поэтому чтобы понять, чей голос нужно купить, понадобится число на 1 меньше: votes_needed – 1.

Чтобы узнать, кто ничего не получил в прошлый раз, нужно сделать так:

# список, кто ничего не получил в прошлый раз — им нужно дать 1 мешок
elvises_to_bribe = [i for i, c in enumerate(prev) if c == 0]

Тут мы смотрим список и с помощью встроенной функции enumerate() получаем номер того грабителя, у которого в списке стоит 0 мешков. Но предыдущий код показывает как бы мысли грабителя на ход вперёд: «Как распределяются деньги, если меня выкинут из фургона?» Это будет в списке elvises_to_bribe.

Поэтому сейчас мы берём увеличенный на 1 человека список и учитываем грабителя, который ещё в фургоне и хочет там и остаться:

# текущий Элвис (старший) пытается выкупить нужное количество голосов
for i in elvises_to_bribe[:votes_needed – 1]:
# +1 потому что текущий список больше на одного грабителя
result[i + 1] = 1
bags -= 1

Эта часть кода распределяет по одному мешку на тех, кто ничего не получил. Оставшиеся мешки получает старший грабитель:

# оставшиеся мешки забирает старший
result[0] = bags
return result

Полный код функции:

def elvises_division(n, bags=100):
   # если остался один Элвис — он забирает всё
   if n == 1:
       return [bags]

   # предыдущий результат для n-1 грабителей
   prev = elvises_division(n - 1, bags)

   # пустой список распределения мешков
   result = [0] * n
   # проверка нужного количества голосов
   votes_needed = (n // 2) + (n % 2)

   # список, кто ничего не получил в прошлый раз, — им можно дать 1 мешок
   elvises_to_bribe = [i for i, c in enumerate(prev) if c == 0]

   # текущий Элвис (старший) пытается выкупить нужное количество голосов
   for i in elvises_to_bribe[:votes_needed - 1]:
       # +1 потому что список сдвинулся на одного грабителя
       result[i + 1] = 1
       bags -= 1

   # оставшиеся мешки забирает старший
   result[0] = bags
   return result

print(elvises_division(5))