Версия для печати темы

Автор: WildKOT 8.3.2015, 22:57

Ответа задачи не знаю.
Поэтому обсуждение открытое. То есть ответы можно писать в теме белым шрифтом.
=============
Большинство населения Мозгограда составляют минимозги, тогда как мегамозги в большинстве.
Именно это позволяло подлым оккупантам постоянно выигрывать выборы в городской совет, обманывая большинство населения.
Городской совет состоит из мэра и 49 представителей. Решение принимается большинством, при этом вес голоса мэра равен полутора голосам рядовых представителей.
Мегамозг собрал команду из 7 соратников, чтобы взять власть, но понял, что подлые оккупанты не позволят ему это сделать просто так. Поэтому Мегамозг согласился добавить в свою команду нескольких оккупантов, а оставшиеся до 49 места занял минимозгами.

Зал заседаний состоит из квадрата 7*7 для представителей и отдельного места для мэра.
Все Мегамозги принимают полезные для города решения, подлые оккупанты - вредные. Минимозги неспособны отличить полезные решения от вредных, поэтому подвержены влиянию соседей - мегамозгов и оккупантов, находящихся в смежных ячейках, голосуя за полезные решения, если число оккупантов слева, справа, спереди и сзади не больше, чем число мегамозгов.

Алгоритм рассадки совета:
Мэр и оккупанты ходят по очереди. Каждый ход, мэр может посадить одного, нескольких или ниодного мегамозга на любые свободные места, после чего оккупанты направляют одного или нескольких своих представителей на выбранные ими места.
Если одна из сторон рассадила всех своих представителей, то другая должна рассадить всех.
После рассадки мегамозгов и оккупантов оставшиеся места занимают минимозги.
Спрашивается, какое максимальное число оккупантов Мегамозг может включить в команду, чтобы не потерять власть?

Автор: SinsI 21.5.2015, 2:38

Похоже что это вариант Го с ограниченным числом камней и неограниченным числом расстановок за ход на доске 7 x 7.
Точно ли в этой задаче есть аналитическое решение, которое можно получить не полным компьютерным перебором вариантов?

Автор: netvoe 21.5.2015, 3:51

"Большинство населения Мозгограда составляют минимозги, тогда как мегамозги в большинстве. "

хотелось бы понять для начала, что сие означает ???

Автор: WildKOT 22.5.2015, 0:09

"Большинство населения Мозгограда составляют минимозги, тогда как мегамозги в большинстве меньшинстве. "



Не гарантируется, но можно предлагать изменение правил, чтобы были.

Автор: SinsI 22.5.2015, 0:33

По прикидке, получается следующее решение:

Каждый ход ставить больше одной фигурки нет смысла. Ходить в крайние вертикали и горизонтали также не выгодно. Каждый раз когда ставится фигурка оккупанта, число его голосов увеличивается на 5. Если стоит фигурка оккупанта, то поставленная фигурка мегамозга отбирает у оккупанта 2 голоса и делает двух минимозгов устойчивыми к одиночному оккупанту. Тогда после расставленных 7 фигурок мегамозгов и 6 фигурок оккупантов у оккупанта будет 6*3 = 18 голосов (первый ход мегамозга холостой). Для выигрыша ему надо 26 голосов, так что необходимо ещё минимум 8 голосов. Три голоса с фигурки он может получить всегда (ходя бы пойдя в боковые стороны), и также возможно что сможет получить и по 4 (например, пойдя в боковые клетки при условии что рядом с ними есть хотя бы по 1 клетке без влияния фигурки мегамозга или где оно компенсировано оккупантом) . Тогда 9 фигурок оккупанту достаточно точно, и возможно что хватит и 8 фигурок.

Автор: 0 22.5.2015, 1:12

Не факт.
ММ может дождаться рассадки всех 9 оккупантов. И уже потом расставлять фигуры с выгодой для себя - "плюсы" оккупантов будут перекрываться (не перекрывая даже 6 плюсов не разместить) и будет шанс отвоевать одним ходом не две клетки а 4.
Количественный критерий тут не сработает - 9 оккупантов могут получить максимум 41 голос заняв a4,b2,b6,d1,d4,d7,f2,f6,g4 но ММ легко бьет такую позицию всего 5ю фигурами b4,d2,d6,f4,g1

Автор: SinsI 22.5.2015, 5:41

Ой. Что-то я прочитал условие что каждый каждый ход должен ставить хотя бы одну. Иначе понятие "хода" бессмысленно - вначале все свои фигурки ставит оккупант а потом мегамозг.

Автор: 0 22.5.2015, 19:21

Все таки сначала мегамозг может поставить несколько фигурок, потом оккупант ставит все свои и затем мегамозг ставит оставшиеся.
Скорее всего на результат не повлияет, но доказательство усложняет существенно.