Задача про Кащея и Ивана

Оказывается, старенькая задача, но я про неё ещё не слышал. Позаимствовано в ЖЖ.

Дано: Кащей Бессмертный, который украл принцессу у Ивана Царевича. И собственно, Иван Царевич, который невесту хочет вернуть.

Кащея убить можно. Есть 10 колодцев с ядом, сила яда от колодцу к колодцу постепенно нарастает. Более сильный яд является противоядием для более слабого (если выпить сначала из 2 колодца, а потом из 3 – отравления не будет). Если смешать два яда, то смесь приобретет свойства сильнейшего.

Сама битва: соперники приходят на ристалище с одним кубком в руках. Отдают кубок противнику, который выпивает содержимое. Но подлец Кащей построил вокруг последнего 10 колодца крепость, которая неприступна для Ивана. Таким образом, у Кащея есть доступ к сильнейшему яду, а у Ивана нет.

Цель: победить Кащея и выжить самому.

Можете подумать, а можете сразу заглянуть в ответ ко мне.

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

Когда я впервые прочел задачку, я подумал, что это как раз для теории игр и таблиц минимакса. Но сначала надо было догадаться обо всех действиях, которые могут совершить игроки. Я разделил эти действия на четыре группы:

  1. Выпить что-то перед боем (или не пить ничего перед боем)
  2. Предложить сопернику какой-то кубок (в кубке может быть яд из колодцев, либо безвредная жидкость, но по вкусу которой невозможно определить яд это или нет)
  3. Смешать содержимое кубка соперника с чем-то (или не смешивать ни с чем), затем выпить
  4. Выпить что-то после боя (или не пить ничего после боя)

Соответственно, Кащей может использовать для каждой группы действий яд из 10 колодцев, а Иван только из 9. Получаем все возможные действия и подсчитываем минимакс в программе.

В игре у Ивана 10000 возможностей, у Кащея 14641
Составляем таблицу минимакса…
Решение
Иван
перед ристалищем выпить яд DRINK_1,
дать сопернику кубок с ядом GIVE_9,
самому смешать данный соперником кубок с ядом MIX_2,
а потом запить ядом NOTHING

Итак, Иван пьет яд из первого колодца, подносит сопернику кубок с 9-м ядом, а сам смешивает содержимое кубка от Кащея с ядом из второго колодца, выпивает и остается жив. Посмотрим на ситуацию со стороны Кащея:

Кащей
перед ристалищем выпить яд NOTHING,
дать сопернику кубок с ядом GIVE_9,
самому смешать данный соперником кубок с ядом MIX_1,
а потом запить ядом DRINK_10

Обладая самым сильным противоядием, Кащей боится только того, что ему Иван поднесет безвредную жидкость, и тогда выпив 10-й яд, он проиграет. Чтобы убедиться в том, что подношение Ивана содержит яд, он просто добавляет первый яд в кубок и запивает своим противоядием. Обратим внимание, на то, что компьютер на месте Кащея предложил выдать 9-й кубок Ивану, а не 10-й. В этом нет никакой скрытой логики, просто сыграл роль порядок оценки действий компьютером. 10-й яд сыграл бы также.

А теперь мы сопоставим этим две тактики друг другу. Вот, что выдал компьютер:

Шансы Ивана на выживание при разумном действии Кащея: выжил

Шансы Кащея на выживание при разумном действии Ивана: выжил

Итак, выбрав лучшие стратегии, оба персонажа остаются живы. Но Иван не достигает свой цели — принцессы. Тогда, может, есть такая тактика, когда один из персонажей умрет? Слово компьютеру:

Умрет ли Иван, если Кащей изберет любой другой вариант действий, а сам будет придерживаться разумной стратегии: нет

Умрет ли Кащей, если Иван изберет любой другой вариант действий, а сам будет придерживаться разумной стратегии: нет

Таким образом, с тем же успехом, Кащей с Иваном могли бы выпить пива друг с другом. Или напоить принцессу каким-нибудь ядом. Всё равно, ни один из них в результате этой игры не получит желаемого результата.

Теперь посмотрим, изменилось ли что-нибудь, если Кащей и Иван были бы в одинаковых условиях и имели бы равный доступ ко всем 10 колодцам. Стратегия их обоих выглядела бы так:

перед ристалищем выпить яд DRINK_1,
дать сопернику кубок с ядом GIVE_10,
самому смешать данный соперником кубок с ядом MIX_2,
а потом запить ядом NOTHING

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

Иван — честный и добрый малый, поэтому он никогда не должен нарушать правила. А вот Кащей — хитрюга, поэтому подумаем ещё немного за него.

Вообще, задача сводится к ничьей, даже если для Ивана останутся два самых слабых колодца, а остальные восемь будут окружены крепостями Кащея. Строить крепости в таком количестве, очевидно, не являлось возможным для Кащея из-за затратности проекта. Но если подумать, то поставив крепость, скажем, на 8-м колодце, Кащей обеспечивает себе безоговорочную победу, но с маленькой хитростью. Он не говорит об этом Ивану, но коварно переливает из 10-го колодца стаканы в колодцы с первого по седьмой и в девятый. Из-за свойств яда, в девяти колодцах из десяти будет самый сильный яд, а самый слабый яд — восьмой будет у Кащея. Запускаем программу:

В игре у Ивана 10000 возможностей, у Кащея 14641
Составляем таблицу минимакса…
Решение
Иван
перед ристалищем выпить яд DRINK_1,
дать сопернику кубок с ядом GIVE_10,
самому смешать данный соперником кубок с ядом MIX_2,
а потом запить ядом NOTHING

Кащей
перед ристалищем выпить яд DRINK_8,
дать сопернику кубок с ядом GIVE_1,
самому смешать данный соперником кубок с ядом MIX_1,
а потом запить ядом NOTHING

Шансы Ивана на выживание при разумном действии Кащея: умер
Шансы Кащея на выживание при разумном действии Ивана: выжил

Умрет ли Иван, если Кащей изберет любой другой вариант действий, а сам будет придерживаться разумной стратегии: да
Умрет ли Кащей, если Иван изберет любой другой вариант действий, а сам будет придерживаться разумной стратегии: нет

Резюме: планируйте бюджеты правильно, мои коварные.

Исходный код программы, которая составляет таблицу минимакса.

Вливайтесь в общение

4 комментария

  1. иван поит кощея бесмертного водой, а сам перед дуэлью выпивает яд. кощей думает, что выпил яд, пьёт 10 яд и погибает, когда он даёт 10 яд ивану, он становится противоядием. если что, в условии задачи сказано, что кощей даст ване 10 яд и выпьет его сам, чтобы спасти себя и убить ивана

  2. Кащей смешает воду, которую дал Иван, с любым слабым ядом, выпьет эту смесь, а потом запьет 10-м ядом — и будет в безопасности

  3. «а сам смешивает содержимое кубка от Кащея с ядом из второго колодца, выпивает и остается жив». Смысла-то? Если Кащей дает 9-10 яд, то общий яд=самому сильному, то есть 9 или 10. Что Иван пил второй яд никому не поможет

  4. По условиям задачи, более сильный яд является противоядием для более слабого (если выпить сначала из 2 колодца, а потом из 3 – отравления не будет). Поэтому Иван пьёт сначала яд из колодца №1, а потом выпивает смесь ядов из колодца №2 и из колодца X, который выбрал Кащей. Такая стратегия гарантирует, что выпитая смесь сильнее, следовательно, является противоядием для яда из колодца №1.

Оставьте комментарий

Ваш e-mail не будет опубликован.