МАЛЫЙ МЕХМАТ МГУ

Кружок 5 класса

Руководители Дмитрий Владимирович Трущин и Михаил Владимирович Шеблаев
2012/2013 учебный год

Принцесса или тигр (23 марта 2013 года).

Сегодняшнее занятие посвящено решению задач из замечательной книги Р. Смаллиана «Принцесса или тигр?», где есть ещё множество других интересных задач.

В каждой из задач имеется две комнаты, в некоторых из которых поджидают проголодавшиеся тигры, а в остальных — прекрасные принцессы. В каждой из комнат всегда кто-то один. Нужно при помощи оставленных на дверях надписей определить, где кто. Но берегитесь! Не все надписи правдивы!

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

1.: На одной из двух дверей написана правда, а на другой — ложь. А надписи такие:
«В этой комнате находится принцесса, а в другой комнате сидит тигр.»
«В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр.»
Указание Примечание Решение

Указание. Рассмотрите разные случаи: каждая из надписей правдива или ложна, или рассмотрите варианты, кто где сидит. В случаях, которые не могут быть, вы придёте к противоречию с уловием задачи.

Примечание. Первая надпись утверждает, что выполняются одновременно два утверждения: «в первой комнате сидит принцесса», и «во второй комнате сидит тигр», то есть, она имеет вид «А и Б». Значит, чтобы первая надпись была ложна, достаточно, чтобы хотя бы одно из этих двух утверждений не выполнялось, то есть либо в первой комнате не было принцессы, либо во второй не было тигра. То есть, отрицание первой надписи «не (А и Б)» имеет вид «не А или не Б».

Решение. Пусть первая надпись правдива. Тогда в первой комнате принцесса, а во второй тигр, и поэтому вторая надпись тоже правдива. Но, по условию, одна из надписей должна быть ложна. Противоречие.
Пусть теперь первая надпись ложна. Она утверждала, что в первой комнате принцесса и во второй тигр. Значит, если она неверна, то неверно хотя бы одно из этого. Тогда либо в этой комнате сидит не принцесса (а сидит тигр), либо во второй комнате нет тигра (а сидит принцесса), а, может быть, и то, и другое. А ещё тогда, раз одна из надписей должна быть верна, то верна вторая надпись. То есть, и тигр должен быть где-то, и принцесса тоже где-то должна быть. Значит, варианты, где в обеих комнатах тигры или в обеих комнатах принцессы не подходят. Остаётся вариант, где в первой комнате тигр, а во второй — принцесса.
2.: А в этой задаче, наоборот, либо на обеих дверях написана святая истина, либо на обеих — подлая ложь.
«По крайней мере в одной из этих комнат находится принцесса.»
«Тигр сидит в другой комнате.»
Решение

Решение. Если вторая надпись верна, то в первой комнате тигр. Кроме того, тогда первая надпись тоже должна быть верна, значит, принцесса должна быть во второй комнате.
Если бы вторая надпись не была верна, то есть в первой комнате была бы принцесса, то первая надпись оказалась бы верна. В то же время, по условию, она должна была бы быть не верна вместе со второй. Противоречие.
3.: И в этой задаче снова, надписи либо обе верны, либо обе нет.
«Либо в этой комнате сидит тигр, либо принцесса находится в другой комнате, либо и то и другое.»
«Принцесса в другой комнате.»
Примечание

Примечание. Первая надпись утверждает, что верно хотя бы одно из двух: тигр в первой комнате или принцесса во второй. Значит, она неверна тогда и только тогда, когда неверно и то, и другое одновременно (иначе было бы верно хотя бы одно из них).
Если за А и Б обозначить её части, то надпись гласит «А или Б». Тогда её отрицание означает «не (А или Б)», то есть «не А или не Б». Вместе с примечанием к первой задаче это означает, что, когда отрицание проносится под операции «и» и «или», они заменяются друг на друга. В логике это называется законами де Моргана.

В остальных задачах все немножко хитрее. Если в первой комнате принцесса, то на двери написана правда, а если тигр — ложь. А если во второй комнате принцесса, наоборот, на двери написана ложь, а если тигр — правда.

4.: «В обеих комнатах находятся принцессы.»
«В обеих комнатах находятся принцессы.»
Указание Решение

Указание. Эти задачи решаются также — перебором нескольких вариантов.

Решение. Если верна надпись на первой табличке, то верна и на второй (ведь надписи одинаковы). Тогда, согласно надписи, в обеих комнатах принцессы. Но, согласно условию, раз на второй комнате верная надпись, в ней тигр. Противоречие.
Тогда обе надписи неверны, то есть хотя бы в одной из комнат должен быть тигр. В первой комнате как раз должен быть тигр, так как на ней ложная надпись. А раз на второй ложная, то во второй принцесса.
5.: «По крайней мере в одной из комнат находится принцесса.»
«Принцесса в другой комнате.»
Примечание Решение

Примечание. Первую табличку можно рассматривать утверждение вида «А или Б», где А = «в первой комнате принцесса», Б = «во второй комнате принцесса», для которых мы показали, что отрицания имеют вид «не А и не Б». Однако можно посмотреть на это с другой стороны. Первая табличка утверждает, что среди этих двух комнат существует комната, для которой верно утверждение А = «в этой комнате есть принцесса». Отрицание от него — «принцессы нет ни там, ни там» — означает, что для любой комнаты выполняется отрицание А. То есть,
«не (существует комната (для которой А)) = для любой комнаты (не А)».
Таблички в прошлой задаче имели другой вид «для любой комнаты (А)», то есть их отрицание представляло собой
«не (для любой комнаты (А)) = существует комната (для которой (не А))».
Таким образом, кроме законов де Моргана, здесь тоже наблюдается симметрия: отрицание ещё меняет «существует» и «для любого» на противоположное.

Решение. Если первая табличка верна, то в первой комнате должна быть принцесса. Значит, вторая табличка тоже верна. Тогда во второй комнате тигр (раз на ней верная табличка).
Если первая табличка не была бы верна, то в обеих комнатах должны быть тигры. Тогда вторая табличка тоже неверна, а значит, во второй комнате должен быть не тигр, а принцесса. Противоречие.
6.: «Что ни выберешь — все едино.»
«Принцесса в другой комнате.»
7.: «Что выбрать — большая разница.»
«Лучше выбрать другую комнату.»
8.: В этой задаче таблички написаны, но еще не повешены на двери, и не ясно, какая куда:
«В этой комнате сидит тигр.»
«В обеих комнатах сидят тигры.»
Указание Решение

Указание. В этой задаче придётся дополнительно рассматривать варианты с разным расположением табличек на дверях.

Решение. 1) Пусть первая табличка висит на первой двери.
1а) Пусть она верна. Тогда, по условию, в этой комнате должна быть принцесса, а табличка говорит, что там тигр. Противоречие.
1б) Пусть она неверна. Тогда, по условию, в этой комнате должен быть тигр, а это значит, что она верна. Противоречие.
1) Итак, первая табличка вообще не может быть на первой двери.

2) Пусть первая табличка на второй двери. Тогда вторая — на первой.
2а) Пусть первая табличка верна. Тогда во второй комнате должна быть принцесса, а табличка говорит, что там тигр. Противоречие.
2б) Остаётся, что первая табличка на второй двери, и она неверна. Значит, во второй комнате принцесса. Тогда неверна и вторая табличка (на первой двери). По условию, это означает, что в первой комнате тигр. Итак, в первой комнате тигр, а во второй — принцесса.


	МАЛЫЙ МЕХМАТ МГУ

ГЛАВНАЯ СТРАНИЦА НАША КОМАНДА О КРУЖКАХ РАСПИСАНИЕ ВОПРОС-ОТВЕТ ЛЕКЦИИ МАТЕРИАЛЫ ЗАНЯТИЙ 5 класс 6 класс 7 класс 8 класс Перечневые олимпиады 2-3 уровень АРХИВ МАЛЫЙ МЕХМАТ — ШКОЛЕ ЛИТЕРАТУРА ССЫЛКИ	Кружок 5 класса Руководители Дмитрий Владимирович Трущин и Михаил Владимирович Шеблаев 2012/2013 учебный год Принцесса или тигр (23 марта 2013 года). Сегодняшнее занятие посвящено решению задач из замечательной книги Р. Смаллиана «Принцесса или тигр?», где есть ещё множество других интересных задач. В каждой из задач имеется две комнаты, в некоторых из которых поджидают проголодавшиеся тигры, а в остальных — прекрасные принцессы. В каждой из комнат всегда кто-то один. Нужно при помощи оставленных на дверях надписей определить, где кто. Но берегитесь! Не все надписи правдивы! Может быть так, что в обоих комнатах кто-то одинаковый. Во всех задачах нужно не только найти подходящую комбинацию, но и доказать, почему другие варианты не подходят. 1. На одной из двух дверей написана правда, а на другой — ложь. А надписи такие: «В этой комнате находится принцесса, а в другой комнате сидит тигр.» «В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр.» Указание Примечание Решение Указание. Рассмотрите разные случаи: каждая из надписей правдива или ложна, или рассмотрите варианты, кто где сидит. В случаях, которые не могут быть, вы придёте к противоречию с уловием задачи. Примечание. Первая надпись утверждает, что выполняются одновременно два утверждения: «в первой комнате сидит принцесса», и «во второй комнате сидит тигр», то есть, она имеет вид «А и Б». Значит, чтобы первая надпись была ложна, достаточно, чтобы хотя бы одно из этих двух утверждений не выполнялось, то есть либо в первой комнате не было принцессы, либо во второй не было тигра. То есть, отрицание первой надписи «не (А и Б)» имеет вид «не А или не Б». Решение. Пусть первая надпись правдива. Тогда в первой комнате принцесса, а во второй тигр, и поэтому вторая надпись тоже правдива. Но, по условию, одна из надписей должна быть ложна. Противоречие. Пусть теперь первая надпись ложна. Она утверждала, что в первой комнате принцесса и во второй тигр. Значит, если она неверна, то неверно хотя бы одно из этого. Тогда либо в этой комнате сидит не принцесса (а сидит тигр), либо во второй комнате нет тигра (а сидит принцесса), а, может быть, и то, и другое. А ещё тогда, раз одна из надписей должна быть верна, то верна вторая надпись. То есть, и тигр должен быть где-то, и принцесса тоже где-то должна быть. Значит, варианты, где в обеих комнатах тигры или в обеих комнатах принцессы не подходят. Остаётся вариант, где в первой комнате тигр, а во второй — принцесса. 2. А в этой задаче, наоборот, либо на обеих дверях написана святая истина, либо на обеих — подлая ложь. «По крайней мере в одной из этих комнат находится принцесса.» «Тигр сидит в другой комнате.» Решение Решение. Если вторая надпись верна, то в первой комнате тигр. Кроме того, тогда первая надпись тоже должна быть верна, значит, принцесса должна быть во второй комнате. Если бы вторая надпись не была верна, то есть в первой комнате была бы принцесса, то первая надпись оказалась бы верна. В то же время, по условию, она должна была бы быть не верна вместе со второй. Противоречие. 3. И в этой задаче снова, надписи либо обе верны, либо обе нет. «Либо в этой комнате сидит тигр, либо принцесса находится в другой комнате, либо и то и другое.» «Принцесса в другой комнате.» Примечание Примечание. Первая надпись утверждает, что верно хотя бы одно из двух: тигр в первой комнате или принцесса во второй. Значит, она неверна тогда и только тогда, когда неверно и то, и другое одновременно (иначе было бы верно хотя бы одно из них). Если за А и Б обозначить её части, то надпись гласит «А или Б». Тогда её отрицание означает «не (А или Б)», то есть «не А или не Б». Вместе с примечанием к первой задаче это означает, что, когда отрицание проносится под операции «и» и «или», они заменяются друг на друга. В логике это называется законами де Моргана. В остальных задачах все немножко хитрее. Если в первой комнате принцесса, то на двери написана правда, а если тигр — ложь. А если во второй комнате принцесса, наоборот, на двери написана ложь, а если тигр — правда. 4. «В обеих комнатах находятся принцессы.» «В обеих комнатах находятся принцессы.» Указание Решение Указание. Эти задачи решаются также — перебором нескольких вариантов. Решение. Если верна надпись на первой табличке, то верна и на второй (ведь надписи одинаковы). Тогда, согласно надписи, в обеих комнатах принцессы. Но, согласно условию, раз на второй комнате верная надпись, в ней тигр. Противоречие. Тогда обе надписи неверны, то есть хотя бы в одной из комнат должен быть тигр. В первой комнате как раз должен быть тигр, так как на ней ложная надпись. А раз на второй ложная, то во второй принцесса. 5. «По крайней мере в одной из комнат находится принцесса.» «Принцесса в другой комнате.» Примечание Решение Примечание. Первую табличку можно рассматривать утверждение вида «А или Б», где А = «в первой комнате принцесса», Б = «во второй комнате принцесса», для которых мы показали, что отрицания имеют вид «не А и не Б». Однако можно посмотреть на это с другой стороны. Первая табличка утверждает, что среди этих двух комнат существует комната, для которой верно утверждение А = «в этой комнате есть принцесса». Отрицание от него — «принцессы нет ни там, ни там» — означает, что для любой комнаты выполняется отрицание А. То есть, «не (существует комната (для которой А)) = для любой комнаты (не А)». Таблички в прошлой задаче имели другой вид «для любой комнаты (А)», то есть их отрицание представляло собой «не (для любой комнаты (А)) = существует комната (для которой (не А))». Таким образом, кроме законов де Моргана, здесь тоже наблюдается симметрия: отрицание ещё меняет «существует» и «для любого» на противоположное. Решение. Если первая табличка верна, то в первой комнате должна быть принцесса. Значит, вторая табличка тоже верна. Тогда во второй комнате тигр (раз на ней верная табличка). Если первая табличка не была бы верна, то в обеих комнатах должны быть тигры. Тогда вторая табличка тоже неверна, а значит, во второй комнате должен быть не тигр, а принцесса. Противоречие. 6. «Что ни выберешь — все едино.» «Принцесса в другой комнате.» 7. «Что выбрать — большая разница.» «Лучше выбрать другую комнату.» 8. В этой задаче таблички написаны, но еще не повешены на двери, и не ясно, какая куда: «В этой комнате сидит тигр.» «В обеих комнатах сидят тигры.» Указание Решение Указание. В этой задаче придётся дополнительно рассматривать варианты с разным расположением табличек на дверях. Решение. 1) Пусть первая табличка висит на первой двери. 1а) Пусть она верна. Тогда, по условию, в этой комнате должна быть принцесса, а табличка говорит, что там тигр. Противоречие. 1б) Пусть она неверна. Тогда, по условию, в этой комнате должен быть тигр, а это значит, что она верна. Противоречие. 1) Итак, первая табличка вообще не может быть на первой двери. 2) Пусть первая табличка на второй двери. Тогда вторая — на первой. 2а) Пусть первая табличка верна. Тогда во второй комнате должна быть принцесса, а табличка говорит, что там тигр. Противоречие. 2б) Остаётся, что первая табличка на второй двери, и она неверна. Значит, во второй комнате принцесса. Тогда неверна и вторая табличка (на первой двери). По условию, это означает, что в первой комнате тигр. Итак, в первой комнате тигр, а во второй — принцесса.	ЗАДАЧИ 5 класс Плюс-минус один Обратный ход Посчитай-ка Скобки и знаки Рыцари и лжецы Движение Движение (доп. задачи) Факториал Комбинаторика (доп. задачи) Математическая абака Комбинаторика Козы Переливания Предновогодний Оливье Математическая карусель Всюду идут дороги Разные задачи Разрезалки Круги Эйлера Принцесса или тигр Магические фигуры Двумя способами Конструкции ЗАДАЧИ ауд. П3 (рук. Л. А. Попов)