Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ3

Конкурсная задача ММ3 (5 баллов)

Некий путешественник, идя по дороге в стране, где живут рыцари и лжецы, встретил группу из нескольких местных жителей. Каждый из встреченных по-очереди произнес две фразы (причем первые фразы зависели от порядкового номера говорящих, а вторые были одинаковы). k-й по счету сказал: «Среди нас не более k рыцарей. Среди моих спутников есть лжецы.» Сколько человек встретил путешественник? Напомню, что в задачках такого типа рыцари всегда говорят правду, а лжецы всегда лгут.

Решение

Проанализируем сначала первые фразы говорящих.
Легко видеть, что последний из говоривших сказал правду.
Предположение о том, что первый из говоривших (при условии, что он не был и последним) был рыцарем сразу приводит нас к противоречию: тогда рыцарей не менее 2-х (первый и последний), но первый утверждает, что их не более одного. Значит, первый - лжец. Но тогда предпоследний сказал правду… Рассуждая аналогично, приходим к выводу:
Если говоривших было нечетное число (скажем, 2s+1), условию задачи не противоречит лишь ситуация, когда первые s человек были лжецами, а последующие s+1 рыцарями. Если же число говорящих было четно (2s), то, из предположения, что s-й говоривший - рыцарь, следует, что его фраза - ложь, а из предположения, что он лжец, вытекает, что он сказал правду.
Полученное противоречие доказывает, что наш путник встретил нечетное число местных жителей.
Теперь обратимся ко второй фразе.
Из нее сразу вытекает, что среди говоривших есть ровно один лжец.
Окончательно получаем, что путнику встретил 3-х аборигенов (первый из говоривших был лжецом, а остальные двое рыцарями).

Награды

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


 

 


Страница: [[marathon:problem_3]]

marathon/problem_3.txt · Последние изменения: 2015/10/03 20:55 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006