Задача 5.
В некотором уезде живут купцы и разбойники. Купцы всегда говорят правду, а разбойники всегда лгут. Однажды за круглым столом собралась компания из 10 жителей, причём известно, что среди них есть хотя бы один разбойник и хотя бы один купец. Какое наибольшее количество из сидящих за столом может сказать: «Один из моих соседей разбойник, а другой – купец»?
Ответ на Задачу 5.
Ответ: 9.
Решение:
Предположим, что все сидящие за столом смогли сказать такую фразу. Тогда рядом с разбойником должны сидеть либо два разбойника, либо два купца. Но если рядом с каким-то разбойником будет сидеть два разбойника, то с его соседом-разбойником также рядом должны сидеть два разбойника. Продолжая рассуждать аналогично, получим, что все сидящие за столом разбойники; по условию это невозможно. Значит, рядом с каждым разбойником должны сидеть два купца. А рядом с каждым купцом должны сидеть один разбойник и один купец. Таким образом, рассадка за столом восстанавливается однозначно:
... − Р − К − К − Р − К − К − ...
Но тогда число сидящих за столом должно делиться на 3, а 10 на 3 не делится. Поэтому все 10 человек не смогли сказать требуемую фразу. Покажем, что 9 из 10 сидящих за столом могли сказать требуемую фразу. Это могло произойти, если люди за столом сидят следующим образом:
– Р − К − К − Р − К − К – К – Р − К − К −
Среди них только купец К не мог сказать требуемую фразу.
