Задача о коварном преподавателе

forester_200

Ниже приводится 1) развёрнутая формулировка одной известной задачи, 2) вариант её формализации и 3) решение в рамках предлагаемой формальной модели. Было бы интересно послушать мнение форумчан.
1. Задача (на самом деле баян, поскольку есть несколько вариантов формулировок, в частности, про приговорённого к смертной казни; какое-то время назад задача обсуждалась на форуме):
В некоем учебном заведении в некоей группе каждый день (с Пн по Пт, включительно) ровно один урок математики. Каждый такой урок может проходить в одном из двух режимов - "обычное занятие на весь урок" или "контрольная работа на весь урок". Как-то в конце одного урока в Пт преподаватель сказал: "На следующей неделе на одном из наших уроков я проведу контрольную, но она для Вас будет неожиданной". Вопрос: сможет ли он сдержать своё слово?
В чём сложность.
1. Предположим, что он сможет сдержать своё слово, и предположим, что КР будет в Пт. Но тогда вечером в Чт все поймут, что КР в Пт, и сюрприза не получится. Значит, Пт железно отпадает. Предположим, что КР будет в Чт, но тогда, поскольку Пт уже отпала, вечером в Ср все поймут, что КР будет в Чт... и т.д. доходим до Пн. В итоге, как кажется, ни один день не может быть подходящим для сюрприза. Однако...
2. Ученики могут провести все рассуждения из п. 1 и успокоиться. Преподаватель, который вполне может догадаться о таком стечении обстоятельств, решит устроить КР в любой день и достигнет-таки эффекта неожиданности.
Для большей ясности отметим, что задачу разумно решать при выполнении следующих естественных условий:
а) На вопрос "устроит ли преподаватель на ближайшем занятии КР?" ученики решают чисто логическим путём, т.е. в коллективе учеников проходят некие закрытые дебаты, в результате которых одерживает верх та или иная точка зрения, и с нею все соглашаются (т.е. исключается, например, решение вопроса путём "подбрасывания монетки", "обращения к ясновидящей" и т.п.). Все эти рассуждения должны быть под силу преподавателю. Аналогично, и преподавтель в своём желании перехитрить учеников (т.е. застать их врасплох) должен руководствоваться некими здравыми рассуждениями, которые должны быть под силу ученикам.
б) Рассуждения могут использовать любую информацию, получаемую на уроках математики (например, настроение преподавателя/учеников, намёки преподавателя/учеников и т.п.).
в) Преподаватель неплохо знает психологию каждого из своих подопечных.
г) Находчивость, житейская смекалка и т.п. у учеников и у преподавателя примерно одинаковы.
2. Формализуем модель (в частности, будет формализовано понятие "неожиданности") и сформулируем вопрос задачи более строго:
Есть два игрока - "преподаватель" и "ученики", а также независимое лицо - "ведущий". Игра состоит из последовательности ходов. Ход таков: каждый из участников втайне от всех пишет на листке цифру 0 или 1 и запечатывает этот листок в конветрт; в начале каждого "урока" оба участника отдают конверты ведущему, который в присутствии обоих игроков вскрывает их, вслух называет цифру из конверта преподавателя (умалчивая о цифре из конверта учеников) и объявляет результат:
- если от преподавателя поступил 0 и ход был не 5-ым по счёту, ведущий объявляет о продолжении игры;
- если от преподавателя поступил 0 и ход был 5-ым по счёту, ведущий объявляет об окончании игры, победителем считаются ученики;
- если от преподавателя поступила 1, а от учеников 0, ведущий объявляет об окончании игры, победителем считается преподаватель;
- если от преподавателя поступила 1, а от учеников 1, ведущий объявляет об окончании игры, победителем считаются ученики.

Новый вариант формализации (14.11.2010)
Есть
1) "преподаватель" - игрок, заинтересованный в выигрыше;
2) "ученики" - некое автоматическое устройство, общие принципы работы которого понятны преподавателю, но точные алгоритмы, прописанные в данной модели устройства, неизвестны; устройство представляет собою некий искусственный интеллект, способный к анализу поведения преподавателя, его мышления и т.п.; устройство просто работает по своим алгоритмам, у него нет стремления лишить "преподавателя" выигрыша;
3) "ведущий" - независимое лицо.
Игра состоит из последовательности ходов. Ход таков: игорок и устройство втайне друг от друга пишут на листке цифру 0 или 1 и запечатывают эти листки каждый в свой конверт; в начале каждого "урока" игрок и устройство отдают конверты ведущему, который в присутствии игрока и устройства вскрывает их, вслух называет цифру из конверта игрока (умалчивая о цифре из конверта устройства) и объявляет результат:
- если от игрока поступил 0 и ход был не 5-ым по счёту, ведущий объявляет о продолжении игры;
- если от игрока поступил 0 и ход был 5-ым по счёту, ведущий объявляет об окончании игры, игрок считается проигравшим;
- если от игрока поступила 1, а от устройства 0, ведущий объявляет об окончании игры, игрок считается выигрывшим;
- если от игрока поступила 1, а от устройства 1, ведущий объявляет об окончании игры, игрок считается проигравшим.
Всюду далее вместо "преподаватель" следует читать - "игрок"; вместо "ученики" следует читать - "устройство".
(Содержательно: для преподавателя 0 и 1 соответствуют намерениям "я в этот день не провожу КР" и "я в этот день провожу КР"; для учеников те же цифры означают соответственно "мы сегодня ждём КР" и "сегодня КР, скорее всего, не будет")
Соответственно, можно говорить, о том что "КР проведена неожиданно", если на некотором ходе преподаватель написал 1, а ученики - 0.
Вопрос: Есть ли выигрышная стратегия для преподавателя? (под стратегией понимается такой "ход мыслей", "запас принципов", "установок" и т.п. преподавтеля, который бы сподвигал его на ходы, заведомо приводящие к победе)
3. Решение в рамках описанной модели:
Всюду далее:
[math]$X_i$[/math] - некоторые содержательные рассуждения преподавателя перед тем, как сделать i-ый ход,
[math]$x_i$[/math] - величина, принимающая значения " "(пробел) и "не"
[math]$N_i$[/math] - величина, принимающая значения 0 и 1.
Докажем, что у преподавателя выигрышной стратегии не может быть в принципе.
Предположим, что такая стратегия у преподавателя всё-таки есть. Согласно этой стратегии преподаватель перед первым занятием рассуждает так: "[math]$X_1$[/math]". Поэтому я [math]$x_1$[/math] проведу контрольную" (соответственно преподаватель пишет на листке цифру "[math]$N_1$[/math]"). Может случиться так, что ученики рассудят следующим образом: "Ясно, что преподаватель будет рассуждать так: "[math]$X_1$[/math]", и потому он [math]$x_1$[/math] должен провести контрольную" (соответственно ученики на своём листке напишут ту же цифру "[math]$N_1$[/math]"). Аналогичное угадывание хода мыслей преподавателя может происходить на всех ходах.
В результате протокол игры будет состоять из пар одинаковых цифр. Очевидно, такой протокол отвечает выигрышу учеников проигрышу игрока, что противоречит предположению.

shpanenoc

Зря ты менял условие, про смертную казнь было правильнее :)
Выигрышная стратегия учеников - готовиться к контрольной каждый день (тождественно 1 в твоей модели). А то, что тебе это не пришло в голову, многое говорит о психологии учеников :)

blackout

В 2 и 3 похоже все правильно, только долго.

forester_200

Зря ты менял условие, про смертную казнь было правильнее

Поясни, пожалуйста, в чём сущностное отличие этих двух формулировок?
Выигрышная стратегия учеников - готовиться к контрольной каждый день (тождественно 1 в твоей модели).
Фишка в том, что у учеников нет задачи предотвратить контрольную. По условию они просто живут, общаются, обсуждают возможность предстоящей контрольной и всё. А вот перед преподавателем стоит задача остаться честным человеком: пообещал - надо выполнить ;)

А то, что тебе это не пришло в голову, многое говорит о психологии учеников
Поясни, пожалуйста, не понимаю.

blackout

Поясни, пожалуйста, в чём сущностное отличие этих двух формулировок?
Вопрос вкуса.
 
Фишка в том, что у учеников нет задачи предотвратить контрольную. По условию они просто живут, общаются, обсуждают возможность предстоящей контрольной и всё. А вот перед преподавателем стоит задача остаться честным человеком: пообещал - надо выполнить

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

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

forester_200

Теперь ясно, пасиб ;)
Ты в части 3 делаешь то же самое - приводишь выигрышную стратегию за учеников (пусть они и не обязательно стремятся к выигрышу чтобы доказать, что ее нет у преподавателя. просто показал более простую выигрышную стратегию за учеников.
Перед тем, как запостить текст, я убрал из него последний абзац, в котором обосновывалось, что единственно возможной выигрышной стратегией для учеников является, как было сказано, писать всё время 1. Но этот фрагмент я удалил, поскольку понял, что к вопросу задачи эти рассуждения не имеют отношения.

antill

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

soldatiki

Неясно, что подается на вход функциям, вычисляющим ответ препода и учеников. Т.е., что здесь является пространством состояний системы ПРЕПОД + УЧЕНИКИ.

shpanenoc

этот фрагмент я удалил, поскольку понял, что к вопросу задачи эти рассуждения не имеют отношения.
Как же, как же. Твой вопрос - есть ли выигрышная стратегия за преподавателя? Мой ответ: нет, потому что есть выигрышная стратегия за учеников.
Фишка в том, что у учеников нет задачи предотвратить контрольную. По условию они просто живут, общаются, обсуждают возможность предстоящей контрольной и всё.
То есть в этой игре у учеников нет цели выиграть? Тогда ученики - не участники игры. Играет учитель сам с собой, а ученики - это скорее явление природы, внешние факторы. Типа расклада карт при игре в пасьянс.

shpanenoc

Неясно, что подается на вход функциям, вычисляющим ответ препода и учеников. Т.е., что здесь является пространством состояний системы ПРЕПОД + УЧЕНИКИ.
В принципе, это ведь и неважно? На очередном шаге оба игрока (каким-то образом, не суть важно) выбирают 0 или 1. Если выбрано 1-0, то выиграл первый игрок, если 1-1 - то второй. Если 0-x на 5-м шаге - то второй.
Есть ли выигрышная стратегия у первого игрока? нет. А у второго? есть.
Проблема в том, что "парадокс заключенного" формализован неудачно.

soldatiki

Да, действительно неважно, от каких параметров "внешней среды" зависит выбор очередного хода игроков. Важно лишь, что набор этих параметров один и тот же. В частности, игрок не может "подглядывать" в листок другого.
Еще раз повторюсь: формализация не точна. Нужно добавить правило: "Группа может написать 1 только один раз"
При такой формализации задача эквивалентна следующей: "Препод загадывает число от 1 до 5. Группа должна угадать это число. Существует ли детерминированная выигрышная стратегия у кого-нибудь из игроков?". Ответ: НЕТ. Нету ни у того, ни у другого. Какого бы ни было множество Х и функция П на нем, всегда в качестве другой функции Г может оказаться копия П. Другой вопрос, как эту П угадать.
Т. е. при разных "запусках" игры группа, говоря неформально, выигрывает в среднем в одном из пяти случаев.

soldatiki

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

antill

"Препод загадывает число от 1 до 5. Группа должна угадать это число. Существует ли детерминированная выигрышная стратегия у кого-нибудь из игроков?"
в теории игр это называется "задача о встрече в Нью-Йорке", только вместо 5 там 2.
суть: каждый загадывает по числу, потом говорят друг другу эти числа. если совпали, то выигрыщ каждого +1. если не совпали, то выигрыш каждого 0.
допускает массу модификаций: различные (не равные) значения выигрышей у игроков, смешанные стратегии и т.д.

shpanenoc

При такой формализации задача эквивалентна следующей: "Препод загадывает число от 1 до 5. Группа должна угадать это число. Существует ли детерминированная выигрышная стратегия у кого-нибудь из игроков?"
Ну это уже совсем упрощение, не имеющее отношения к "парадоксу узника". И вообще, вот Википедия прекрасно все раскладывает:
Эквивалентной формулировкой будет следующая. Пусть некто мистер Смит даёт коробку и говорит: «Откройте её, и вы неожиданно обнаружите внутри яйцо»

forester_200

То есть в этой игре у учеников нет цели выиграть? Тогда ученики - не участники игры. Играет учитель сам с собой, а ученики - это скорее явление природы, внешние факторы. Типа расклада карт при игре в пасьянс.
У меня пока нет твёрдого понимания этого момента, но, похоже, здесь действительно "ученики" - это некая "внешняя среда", некоторым образом "отзывающаяся" на ходы преподавателя. Единственное "заинтересованное лицо" - это преподаватель, пытающийся разгадать законы, по которым живёт "внешняя среда". Короче говоря, создаётся впечатление, что здесь, строго говоря, нет игры (предполагающей не меньше двух заинтересованных в выигрыше игроков).
Некоторая, может быть, отдалённая, аналогия. Неопытный метатель ядра выходит на поле и несколько раз, под разными углами, бросает ядро. Цель - бросить так, чтобы ядро приземлилось как можно дальше от места броска. Перед каждым разом человек продумывает готовящийся бросок, обращаясь к своему скудному опыту, интуиции и т.п., а также анализируя результаты предыдущих бросков. Законы кинематики, гравитации, сопротивления воздуха и т.п. здесь не являются заинтересованными игроками, но, тем не менее, в каждом случае в зависимости от характеристик запуска эти законы "определяют" место падения шарика.

1853515

ну блин, просто препод решил споить и вы*бать преподшу по-русскому языку и, т.к. у нее опосля будет похмелье и она попросит его ее подменить (не зря ж трахались вместе! то он неожиданно придет и даст им контрольную по-русскому языку :grin:

avgustinka

Докажем, что у преподавателя выигрышной стратегии не может быть в принципе.
чистой выигрышной стратегии у него нет, а рандомизированная — вполне себе есть.

forester_200

В старт-посте новый вариант формализации задачи (написан красным который, на мой взгляд, более адекватно отражает реальную ситуацию. А именно, то, что в реальной жизни ученики не стремятся к выигрышу - они просто живут, общаются, обсуждают возможность контрольной и т.п., короче, подчинены некоторым "психологическим законам". Каждый раз их ответ (0 или 1) есть своего рода "автоматический рефлекс" на окружающую обстановку, а не результат вынашивания коварных планов о срыве "честного проведения контрольной".

blackout

Ничего не изменилось. Странно, что ты этого не замечаешь.

forester_200

Изменилось то, что при таком подходе понятие "выигрышная стратегия учеников" (с самого начала бессмысленное!) теперь не будет использоваться в обсуждении.
Точнее: при таком подходе бессмысленность понятия "выигрышная стратегия учеников" очевидна, как мне кажется, очевидна с самого начала.

blackout

Это полезное и удобное понятие.

antill

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

forester_200

Ребят, я не обсуждаю полезность, удобность и широту применения понятия "выигрышная стратегия" в теории игр. С этим никто не спорит ;) Также я не претендую на широкие познания в теории игр, поскольку имел с нею дело всего лишь на уровне школьных олимпиадных задач. Интересуюсь темой как любитель, надеясь привлечь в трэд людей, способных высказаться компетентно или подкинуть ясные и интересные мысли по существу.
Подскажите, пожалуйста:
1. Допустима ли предложенная формализация в теории игр? Достаточно ли она чёткая, "формальная" и т.п., чтобы рассматриваться в качестве предмета строгой теории?
2. Если да, то верно ли, что при такой формализации понятие "выигрышная стратегия" по отношению к устройству лишается смысла?

blackout

верно ли, что при такой формализации понятие "выигрышная стратегия" по отношению к устройству лишается смысла
Выигрышная стратегия "устройства" - стратегия при которой "игрок" проигрывает.

forester_200

:confused: :confused: :confused:
Пойду думать...

forester_200

Один из участников форума признался, что мои ответы производят на него впечатление, будто я "плюю в сторону теории игр". Ни в коем случае!
Наоборот, моё единственное желание - разработать такую формализацию, чтобы расправиться с задачей строго в рамках теории игр. По-моему, это единственная возможность добыть удовлетворительное решение проблемы.

Mausoleum

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

april75

вставлю свои пять копеек... правильно написал, что есть четкая стратегия выигрыша учеников- готовиться каждый день. С другой стороны, есть правило по умолчанию-каждый день-полный урок или КР. Это правило является жестким, но в реальности между учителем и учениками не оговаривалось, поэтому я бы дал маленькую КР на неполный урок, во второй его половине

shpanenoc

О , чего ты хочешь от нас?..
Теперь твоя задача фактически эквивалентна следующей.
Мужик (=преподаватель=игрок) приходит в казино к рулетке(=ученики=устройство). Он пропускает X раундов (0<=X<=4, это символизирует его ответы 0 затем ставит все свои деньги на зеро.
Есть ли у него выигрышная стратегия?
Твой ответ: Если бы стратегия существовала, то рулетка ведь может рассуждать так же, как и мужик, построить точно такую же стратегию и на X+1-м шаге выкинуть 14 (а не зеро).
Мой ответ: Если рулетка 5 раз подряд выкинет 32 (а не зеро то какая бы ни была стратегия мужика, он проиграет. Так что стратегии нет.
Оба ответа верны :)
P.S. заметил у тебя, что в устройстве запрещена случайность. Изволь, пусть вместо рулетки будет автомат - "однорукий бандит" (раньше такие на улице стояли, и у ФДС-4 в магазине ГУМ-Спорт который показывает на экране 3 цифры, а вместо "зеро" - сочетание 777. Внутри автомата нет физического генератора случайности, а есть алгоритм генерации псевдослучайных чисел. Так что все строго логически алгоритмизуемо, но без random seed-а понять, что он теперь выкинет, не получится.
"ученики" - некое автоматическое устройство
есть
общие принципы работы которого понятны преподавателю
есть
но точные алгоритмы, прописанные в данной модели устройства, неизвестны
есть
устройство представляет собою некий искусственный интеллект, способный к анализу поведения преподавателя, его мышления и т.п.
ну кто его знает, однорукого бандита? Может, он и способен анализировать мышление и поведение, только не использует эту способность?..
устройство просто работает по своим алгоритмам, у него нет стремления лишить "преподавателя" выигрыша
все правда
Оставить комментарий
Имя или ник:
Комментарий: