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

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

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

Рыцари и лжецы (20 октября 2012 года)

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

1.: Давным давно островитянин Дерб сказал своим друзьям: - Вчера мой сосед заявил мне, что он лжец! Кем является Дерб — рыцарем или лжецом?
Ответ Решение

Ответ. Лжецом

Решение.
Так как про соседа Дерба неизвестно, кем он является, то придётся рассмотреть два случая.

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

2. Если сосед Дерба - лжец, то он сказал Дербу неправду, то есть неправда, что он лжец. Снова противоречие.

Итак, если бы сосед Дерба сказал ему, что он лжец, то в любом случае получилось бы противоречие, то есть, такого быть не могло. Вывод: сосед Дерба этого вообще не говорил! Значит, Дерб лжёт.
2.: Как-то раз встретились два островитянина и один сказал другому: «По крайней мере один из нас – лжец». История умалчивает, ответил ли ему на это что-либо собеседник. Тем не менее определите, кем являются оба.
Ответ Указание Решение

Ответ. Первый - рыцарь
Второй - лжец

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

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

Значит, он рыцарь. Тогда он сказал правду, значит, один из них лжец. Поскольку про первого уже знаем, что он рыцарь, то лжецом может быть только второй.
3.: В другой раз встретились два островитянина Абыр и Валг. - По крайней мере один из нас – рыцарь, - глубокомысленно изрек Абыр. - Но ты то уж точно лжец! – рассмеялся ему в лицо Валг. Определите, кем являются оба.
Ответ Указание

Ответ. Абыр - рыцарь
Валг - лжец

Указание. Как и в прошлой задаче, рассмотрите разные случаи, предполагая, что первый островитянин является рыцарем или лжецом.
4.: Однажды в четверг после дождя между островитянами Тимом и Томом произошел следующий диалог: - Ты можешь сказать, что я рыцарь, - гордо заявил Тим. - Ты можешь сказать, что я лжец, - грустно ответил ему Том. Кем являются Тим и Том?
Ответ Решение

Ответ. Тим - лжец
Том - рыцарь

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

Значит, Тим — лжец. Тогда Том не может сказать, что он рыцарь, то есть Том не может сказать неправду. Значит, Том рыцарь. И действительно, слова Тома — правда, потому что Тим может соврать, сказав, будто Том лжец.
5.: Некогда перед судом предстали три островитянина, которых для конфиденциальности мы обозначим А, Б и В. Известно, что преступление совершил ровно один из них, но кто из них является рыцарями, а кто – лжецами, было неизвестно. - Б лжец. Но преступление совершил В, - заявил А. - А и В либо оба рыцари, либо оба лжецы, - сообщил суду Б. - Б говорит правду. Но тем не менее он и совершил преступление, - сказал В. Поразмышляв недолго, судья не только сумел определить, кто есть кто, но и изобличить преступника. А вы сумеете это сделать?
Ответ

Ответ. А - рыцарь
Б - лжец
В - лжец, преступник
6.: В клетках квадрата 4x4 стоят островитяне. В некоторый момент каждый из них произнес: «Во всех соседних со мной клетках стоят лжецы». Какое наибольшее количество лжецов могло быть среди них?
Ответ Указание Решение

Ответ. 12
Не забудьте доказать, что больше нельзя.

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

Решение. Рядом с каждым лжецом должен быть хоть один рыцарь, а рыцарей друг с другом рядом быть не может. Четырёх рыцарей можно легко расставить в квадрате так, чтобы остальное заполнилось лжецами (например, поставив рыцарей по углам). Тогда лжецов будет 4x4 - 4 = 12. Мы привели пример, что такое количество лжецов может быть. Докажем, что это ответ, то есть что больше нельзя. Лжецов можно было бы сделать больше только за счёт уменьшения количества рыцарей. Разобьём квадрат 4x4 на 4 квадратика 2x2. Докажем, что в любом из них должен обязательно быть рыцарь. Действительно, в противном случае весь квадратик 2x2 заполнен лжецами, а лжец, находящийся в углу большого квадрата, не будет соседствовать ни с каким рыцарем, что невозможно. Поскольку квадратиков 2x2 4 штуки, то и рыцарей меньше 4 быть никак не может.


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

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