Математические задачки. Морковкин, скучаем :-)

"О сколько нам открытий чудных!..."

 

Пять человек с нашего форума сыграли турнир по шахматам в 1 круг. После окончания турнира выяснилось, что опытный перворазрядник выиграл ровно две партии, Локомотив свел все партии вничью, дикий Муцио проиграл всего одну партию, причем тому, кто занял 5 место, а Владрусс набрал на пол-очка больше, чем Диамонд. Определите результаты всех шахматистов (в шахматах за победу игрок получает 1 очко, за ничью – пол-очка).

 

Васа - выиграл у Диаманда и Владруса
Локомотив- все ничьи
Владрус - проиграл Васе, выиграл у Диаманда, 2 ничьих
Муцио - проиграл Диаманду, остальные ничьи
Диаманд - выиграл у Муцио,ничья с Локомотивом, 2 другие проиграл
Вроде единственный расклад, единственное - непонятно, почему Муцио выше Диаманда - может по коэффициенту?

 

А вот еще похожую задачу знаю про турнир. В чемпионате гостевой КС играли 6 шахматистов, по одной партии каждый с каждым. ГМ Шипов набрал 4 очка и занял 1-е место, Дмитрий Бирюков занял 2-е место, дикий Муцио и опытный перворазрядник разделили 3-4-е места, Диамонд занял 5-е место, а Локомотив, занявший 6-е место, выиграл личную встречу у опытного перворазрядника. 5 партий турнира закончились вничью, причем известно что Дмитрий Бирюков сделал только одну ничью. Можно ли здесь однозначно восстановить результаты всех партий?

 

Не может Диамант занять предпоследнее место!

 

Симпатичная шахматно-логическая задача от финского решателя Кари Кархунена:
Какой первый ход должны сделать белые, чтобы исключить всякую возможность 5...NxR# (на пятом ходу черный конь бьёт ладью с матом)? Корректность задания проверена компьютером.

 

Ну при 1.е4 или там 1.f3 такая партия возможна. Значит эти 2 хода отпадают 100%.

 

Интересная задача. Все ходы кроме 1.е3 и 1.с3 опровергаются элементарно. Но вот французская и Каро-Канн во второй руке... обе защиты выглядят крепко.

P.S. Пожалуй, повторюсь. Последние сообщения, безусловно, немало занимательны и поучительны. Однако они имеют сугубо шахматный, а не общематематический характер. Будет весьма прискорбно, если все эти задачи потонут в тридцатых страницах темы "Морковкин, скучаем".

Тем более, что в мастерской была подобающая тема "Необычные задачи-головоломки".

 

Опытный перворазрядник играет 8 шахматных партий против 8 элитных гроссмейстеров мира. Он играет хуже, чем каждый из гроссмейстеров, поэтому вероятность выигрыша им каждой партии равна 0.01. Найдите вероятность того, что Вася выиграет хотя бы одну партию.

 

7.73%

 

а сам я знаете какую задачу нашел? играли 4 игрока в 1 круг. Это были опытный перворазрядник, дикий Муцио, Камон и Априлия.
Известно что.
1. У перворазрядника Васи в сумме столько очков, сколько у остальных вместе.
2.У дикого Муцио в сумме столько ничьих, сколько их у остальных участников вместе.(в одной его партии был пат).
3. У Камона в сумме столько проигрышей, сколько их у остальных трех вместе.
Восстановите результаты всех партий.

 

ххх вас апр кам муц
вас *** 1 1 1
апр 0 *** 1 1/2
кам 0 0 *** 1/2
муц 0 1/2 1/2 ***

 

Коллега приятно удивил: подкинул задачку типа мне не ведомого.

6 пиратов делят неделимый клад (т.е. клад достанется только одному).
У пиратов есть строгий ранжир.
Процедура дележа. Старший предлагает распределение. Все голосуют независимо друг от друга, используя два критерия:
а) выжить - приоритетный критерий
б) максимизировать прибыль
Предложение принято, если половина или больше проголосовала "за".
Если предложение не принято, старшего убивают, и процедура повторятеся.

Как пройдёт процесс дележа?

Обобщение: пиратов Н, дублонов С.

ПС в процессе анализа выяснилось, что поведение пиратов по приведённым двум критериям не всегда детерминировано (иногда поуху, как голосовать), но этим можно пренебречь. Если поведение не определено, то по старшему критерию нужно бояться голосования "против".

 

Если пираты, при прочих равных голосуют за, ничего интересного не происходит, клад всегда забирает первый. Доказательство индукцией по числу пиратов. Для одного или двух пиратов все очевидно. Пусть пиратов n>2 и для n-1 пирата все доказано. Тогда первый претендует на клад и голосует за это. Второй против. Остальным в случае убийства первого все равно ничего не светит (по индукционному предположению) и они голосуют за. Первый получает клад, что и требовалось доказать. Интереснее ситуация при которой клад можно делить (100 дублонов), а пираты при прочих равных голосуют против (что по-моему более жизненно). Эту задачу я уже решал, так что дам подумать остальным.

 

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

 

Попробую начать с конца. Осталось двое (5 и 6-й). Для этих двух нет критерия а(они в любом случае будут живы), и есть только критерий б).5-й предлагает отдать клад себе, голосует "за" и получает его (есть 50%).
... и только что увидел что клад неделимый Но начать с конца наверное правильно.

 

Попробую развить мысль. 6-му невыгодно оставаться наедине с 5-м. Осталось трое:
1.1)4-й предлагает клад себе - остальные против (5-й потому что хочет остаться с 6-м, 6-й - см п.1.2)) и 4-го убивают
1.2)боясь голосования 6-го "против", отдает клад ему - зато остается жив.
1.3)Но он также может отдать клад 5-му (вместе они наберут два голоса).
Осталось четверо.
2.1)3-й предлагает клад себе - остальные против (4-му в принципе по барабану - если останется трое то он выберет пункт1.2 или 1.3. и все равно останется жив, 5-й против потому что остаются шансы на сценарий 1.3, 6 против потому что остаются шансы на 1.2) и 3-го убивают. Хотя вместе с 4-м они набрали бы 50% в голосовании, из-за страха что 4-й будет против, 3-му лучше так не распределять.
2.2)3-й предлагает клад 4-му. 5 и 6 против (остаются шансы на 1.3 и 1.2). 3 и 4 за - клад получает 4-й.

пока остановлюсь для проверки остальными юзерами.

 

В изначальной формулировке все действия пиратов детерминированы и вероятностям взятся неоткуда. Можно порешать другую задачу. Допустим пират ценит свою жизнь бесконечно больше чем клад, чужую жизнь совсем не ценит, при прочих равных поступает случайным образом. Тут действительно возникает нетривиальная ситуация:
Тогда при 1 и 2 пиратах клад получает первый.
При 3 пиратах единственная стратегия первого — предложить клад №3.
При 4 пиратах — предложить клад №2 или №3.
При 5 пиратах №1 уже рискует жизнью. Лучший шанс предложить клад №3 или №4. Один из них будет против, получивший клад за и остальным двум все равно.
При 6 пиратах №2 будет голосовать за (иначе он рискует жизнью). Поэтому клад можно дать любому с №3 по №6. Первый выживает гарантировано.
При 7 пиратах лучший шанс дать клад любому с номером от 4 до 7. Два голоса за, два против и троим все равно.
При 8 пиратах №2 всегда за, клад идет номерам с 5 по 8. Трое -за, двое против, троим все равно.
При 9 пиратах №2 и №3 голосуют за (увеличивая шансы на выживание). Клад предлагается пиратам №6-№9. Четыре гарантированных голоса за.
При 10 пиратах №1-№4 голосуют за, клад можно давать №5-№10. №1 выживает гарантировано.
Общий принцип понятен. Осталось слегка подумать и сформулировать правило

—- добавлено: 11 июн 2014, опубликовано: 11 июн 2014 —-

Решение для общего случая.
Типичная ситуация выглядит так: в начале списка есть несколько потенциальных смертников (они всегда голосуют за, чтобы повысить шансы на выживание). В конце списка несколько претендентов на клад (для максимизации шансов клад надо предложить одному из них). Пиратам из середины списка все равно и они голосуют случайным образом. Когда смертников становится много, голосование выигрывается автоматически. Число смертников падает до нуля, а число претендентов на клад возрастает. И далее по циклу. Осталось понять при каком числе пиратов голосование выигрывается гарантировано.Это 1,2,3,4,6,10,18,34,66 ... каждое следующее число это (предыдущее) х 2-2. Общая формула: 2^n+2. Например при 34 пиратах №1-16 (2^4) будут за из страха за свою жизнь, а остальные 18 (2^4+2) пиратов претендуют на клад. Далее на клад будут претендовать 18 последних пиратов, пока их число не достигнет 66. Ну и так далее...

 

Моё решение задачи с неделимым кладом. Сразу ответ: все живы, а клад с равной вероятностью останется у кого-то из последних четверых.

Начнём почти с конца.

Если дело вдруг дойдёт до 5-го раунда (на самом деле не дойдёт, и это мы увидим ниже), то 5-й безнаказанно заберёт клад себе, и на этом конец.

В 4-м раунде, если до него дойдёт (на самом деле не дойдёт), участвуют три пирата: 4-й, 5-й и 6-й. 4-й вынужден отдать приз любому из оставшихся, иначе погибнет. Ведь 5-й и 6-й могут голосовать, не заботясь о своей безопасности (см. раунд 5). И один из них (тот, кому 4-й посулит приз) проголосует "за", обеспечивая конец дележа. В итоге, как видим, эти пираты всегда остаются живы.

В 3-м раунде, если до него дойдёт (на самом деле не дойдёт), участвуют четыре пирата: 3-й, 4-й, 5-й и 6-й. Председательствующий 3-й пират не может пытаться оставить клад себе (чревато), а из оставшихся никого не предпочитает, так что случайным образом предлагает кандидатуру на получение приза из оставшихся 3-х. Сам голосует "за". Остальные трое голосуют без опасения за жизнь. Один из них (а именно, тот, кого выбрал председатель), даёт второй голос, обеспечивая принятие решения. Таким образом, делёж всегда заканчивается не позже 3-го раунда, и 3-й тоже всегда остаётся жив. Однако, без клада. Разве что его наделят кладом в одном из первых двух раундов. Но эту возможность мы сейчас рассмотрим.

Во 2-м раунде, если до него дойдёт (на самом деле не дойдёт), участвуют пять пиратов: 2-й, 3-й, 4-й, 5-й и 6-й. Председательствующий 2-й пират не может пытаться оставить клад себе (чревато), а из оставшихся никого не предпочитает, так что случайным образом предлагает кандидатуру на получение клада из оставшихся 4-х. Троих из них он обделяет, и они, абсолютно не рискуя жизнью (см. итоги 3-го раунда), голосуют против. В результате (если, конечно, дело доходит до этого раунда), 2-й всегда погибает, а клад остаётся пока нераспределённым.

В 1-м раунде участвуют все шестеро, и для принятия решения нужно 3 голоса. Один голос "за" даст 1-й, который не хочет погибать. Второй голос всегда даст 2-й, чтобы тоже не погибнуть (см. итоги 2-го раунда). Третий голос даст тот, кто будет назван в качестве кандидата на клад. Т.е., председатель, чтобы остаться в живых, должен посулить клад кому-то из последних четверых пиратов. И всё тут срастается - все живы-здоровы, решение принято в пользу кого-то из номеров 3, 4, 5, 6. И 2-й раунд не требуется.

Сначала написал этот текст, потом прочитал другие решения. Совпало с Looser.

 

Надо четко сформулировать алгоритм действия пиратов, от этого зависит ответ. Если пираты в неопределенной ситуации действуют случайно, то при трех пиратах первый должен отдать клад третьему, но не второму. Иначе второй понимает, что получит клад в любом случае, а значит может проголосовать против. Ваши пираты злые, они в безопасной ситуации голосуют против, если им не предложить клад. Впрочем, при 6 пиратах наши ответы совпадают.

 

Да, в 4-м раунде у меня этот момент не продуман был. Но ответ это не изменит, потому что эта ситуация в 4-м раунде вроде никак влияет на решения пиратов в 3-м раунде.

Мои пираты не злые. Они корыстные. Нет ситуации, когда они голосуют "против" назло. Голосуя против, они вроде бы всегда повышают вероятность получения клада.

 

Даю вводную. Увеличим детерминированность поведения: тот, кто получил весь вклад, обязан голосовать "за".
Второе: анализ ситуации с большой суммой показывает, что пираты, действуя постериори, то есть после факта объявления дележа, получают от старшего очень мало, что совершенно нежизненно, поскольку в их руках жизнь жеребящего.
Наделим пиратов правом голосовать против (даже в ущерб себе) в наказание делящему, если он предложил меньше матожидания в случае своей смерти.

ПС - неаккуратно выразил мысль. можно голосовать против, если делящий предложил меньше матожидания в случае, если он знает, что за это могут застрелить.


(Придумал сам и ещё не разобрался до конца)

Но сначала, в порядке нарастания сложности, рекомендую неделимый приз с произвольным числом пиратов (по старым правилам).

 

Не совсем так. В общем случае появляется группа пиратов, которым все равно.

Это не слишком изменит решение. Начиная с 6 пиратов никакой разницы.

Нужны дальнейшие уточнения.

 

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

 

Тогда в случае неделимого клада, мы попадаем в решение Бульдозера. В случае делимого клада можно купить нужное число голосов буквально за копейки. Как смоделировать реальное поведение пиратов, я не знаю.

 

Про копейки я говорил - это правило наказания за жадность - там за копейки не откупишься (хотя шанс остаться при деньгах остаётся).

 

Непонятно как в этом случае описывать поведение пиратов. Вот другая, совсем простая ситуация.
Двум людям предлагают 100 евро. Первый предлагает способ дележа, а второй соглашается или нет. В случае отказа никто ничего не получает. Понятно, что оптимальная стратегия — брать себе 99 евро. Понятно, что в реальной жизни это не работает. Придумать "жизненную" модель весьма не просто. А с пиратами все еще сложнее.

 

Хорошо, излагаю на пальцах.
Даём право отстреливать за жадность.
Н=3. Допустим, поведение среднего не определено, даже если он получит всю сумму. Значит, старший должен отвалить младшему за его голос.
Поскольку младший - единственный продавец, то он вправе затребовать всю сумму, иначе будет против.
Исходя из всеобщей рациональности, средний гарантирует страшему жизнь в случае получения всей суммы. повышая таким образом свои шансы на получение денег. Теперь младший и средний имеют матожидание С:2.
Значит, старший может купить купить голос младшего за половину суммы.

 

Вот этого я не понимаю. Ну допустим младший требует всю сумму. А старший все равно предлагает ему копейку. Отказываться нерационально, иначе вообще ничего не получишь. Ну ладно, допустим младший пират за копейку голосовать не будет. Тогда почему-бы среднему пирату не продать свой голос чуть дешевле? А младшему еще сбавить цену. В реальной жизни все так и будет, но как все это формализовать?

 

Наверное, правильным для будет коллективный сговор. Средний обязается не стрелять, если получит сумму, младший обязуется стрелять, если получит меньше, чем всё. Держа цену рынка, младший и средний максимизируют своё матожидание. А готовность продаться за меньшее матожидание картеля уменьшает.
Соответственно, для 4 ситуация такая же, как и с неделимым вкладом.
Интереснее с пятью: здесь нижние три чешут руки отстрелить старшего, имея в перспективе одну треть, но он может предложить им по одной трети и закрыть вопрос, сохранив себе жизнь. Для 6 картель трёх уже не работает, надо разбираться.

 

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

 

Переформулирую мой вариант задачи.
Есть делимой сокровище, ранжир пиратов и критерии сохранения жизни и жажда наживы.
Перед голосованием каждый объявляет свой критерий, по которому он обязуется проголосовать за, если критерий выполнен, и против, если критерий не выполнен. (поведение, таким образом, полностью детерминировано).
Разрешены картели: сговор пиратов, которые выставляют коллективные условия.

После довольно занятного разбора получился не очень интересный ответ: рулят расстрельные картели - картели, которые имеют минимальное достаточное число голосов для расстрела. Он их предложения "трудно отказаться", всё заканчивается за один тур, и каждый член получает равную часть приза. Для случаев Н больше 6 ничего больше и нет, а на малых ситуация чуть интереснее: там могут работать "оправдательные картели": картели, которые не могут расстрелять, но могут спасти.
Для Н=6 может быть два оправдательных картеля по два пирата (все требуют половину приза), с матожиданием одна четверть, таким же, как у расстрельного картеля из 4 человек (дальше гуманизм не может конкурировать с кровожадностью).

 

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

Собственно, случаи Н<=6 подсказывают, как обстоит дело. От младших старшим, Ж - живой Т-труп

ЖЖЖЖТЖ

в общем случае корневая группа - группа трупов - счастливчик - группа трупов - счастливчик и тп.

Формула для номеров счастливчиков.

N(i) = 2**(i+1) +2 | i=0, 1, 2...

N(0) - размер корневой группы.
При достаточно большой группе смертность может составить почти половину группы, в среднем четверть.

 

В моем решении тоже была формула 2^n+2 — число пиратов, при котором первый всегда выживает. Действительно, в худшем случае погибает почти половина. Неясно, как считалось среднее число погибших.