Пардон, лучше так: "Вася состоит в интимных отношениях со своим другом, причём среди Васиных друзей нет геев. Возможно ли это? Ответ поясните."
Пример с "родителями" у меня не получился. Задумка была в том, что мать тоже можно назвать "родителем". Но нет, согласно словарям, "родитель" - это только отец. А вот "друг" - прекрасное слово для подобных загадок. Можно ссылаться не только на словари, но и на Пушкина.
-- 31.10.2015, 03:57 --«Пять пиратов на острове должны разделить между собой сотню золотых монет. Они делят свою добычу так: старший пират предлагает, как делить добычу, а потом каждый голосует, соглашаясь с его предложением или нет. Если по меньшей мере половина пиратов проголосует «за», они поделят монеты так, как предложил старший пират, если же нет — они убивают старшего пирата и начинают все сначала. Самый старший пират (из тех, кто выжил) предлагает новый план, за него голосуют по тем же правилам, а потом или делят добычу, или убивают старшего пирата. Процесс продолжается до тех пор, пока какой-то план не будет принят. Допустим, вы — старший пират. Как вы предложите разделить добычу? (Все другие пираты — жадные, мыслят очень логично, и все они хотят жить.)»Ещё надо бы добавить условия: 1) все пираты разного возраста, 2) голос старшего пирата тоже учитывается.
Пусть пиратов
, а монет
. Рассмотрим случай
: один пират забирает всё себе. Рассмотрим
, два пирата: старший и младший. Старший предлагает: младшему 0, старшему всё (назовём это 2-Схема). Старший голосует за, младший против. Половина «за» – предложение принято.
Далее рассмотрим
. Если старший заберёт всё себе, то ему несдобровать: двое будут против. Значит, надо отстегнуть другим. Кому и сколько? Старший должен заметить, что если среднему дать хоть чуть меньше всей суммы, он всё равно будет против старшего, поскольку если старшего порешат, то средний возьмет всю сумму себе на следующем шаге (по 2-Схеме). Поэтому среднему нет смысла ничего давать. Значит, надо отстегнуть только младшему. Сколько? Достаточно одной монеты. Если младший проголосует против одной монеты, то на следующем шаге не получит ничего (по 2-Схеме). Поэтому младший будет «за». Итак, старший должен дать одну монету младшему, ничего среднему, и
себе (назовём это 3-Схемой). Младший будет «за», средний «против», старший «за». 3-Схема принята.
По аналогии составим
-Схему. Пусть пиратов
и они пронумерованы по возрасту (1-й это самый младший). Старший даёт по одной монете
–му,
-му и т.д. (Тут предположим, что
достаточно велико.) Остальным ничего. Остаток- старшему. Получивших монету назовём Имущими, не получивших – Неимущими.
Теперь сформулируем
–Утверждение: если пиратов
, то старший предлагает
-Схему, Имущие голосуют «за», Неимущие «против», и
-Схема принимается (голосов «за»
для чётного
или
для нечётного).
Теперь докажем, что если
-Утверждение истинно, то и
-Утверждение будет истинным. Пусть пиратов
. Старший предлагает
-Схему. Неимущие будут «против», поскольку им нечего терять, а если
-Схема не будет принята, то они из Неимущих станут Имущими на следующем шаге (поскольку
-й пират, став старшим, предложит
-Схему, и она будет принята по
-Утверждению). Каждый Имущий понимает, что его голос «против» сорвёт
-Схему, и он из Имущего превратится в Неимущего на следующем шаге (по
-Утверждению). Поэтому Имущие будут «за»
-Схему. Старший может отстегнуть Имущим и больше чем по одной монете, но это ему невыгодно (он жаден). Итак,
-Схема будет предложена и принята. Любая другая схема потребует либо большего расхода монет, либо при том же расходе будет сорвана жадными Неимущими (хоть свою монету они и получат, но эта монета им гарантирована на следующем шаге по
-Утверждению, а так у них есть шанс стать старшими и сорвать куш с помощью
-Схемы).
Таким образом, из
–Утверждения следует
–Утверждение. Для
Утверждение тоже истинно, как мы показали выше. Таким образом, по индукции для любого
будет принята
-Схема.
Для
и
старший даёт по монете 1-му (младшему) и 3-му (среднему), себе берёт 98.
Не рассмотрен случай, когда M недостаточно велико для реализации
-Схемы. Но тогда старший в любом случае не жилец.