Задача 5.
В некотором уезде живут купцы и разбойники. Купцы всегда говорят правду, а разбойники всегда лгут. Однажды за круглым столом собралась компания из 12 жителей, каждый из них сказал: «Среди моих соседей есть разбойник». Какое наибольшее число из сидящих за столом может сказать: «Среди моих соседей есть купец»?
Ответ на Задачу 5.
Ответ: 8.
Решение:
Заметим, что два разбойника не могут сидеть рядом (иначе каждый из них сказал бы правду). Значит, никакой разбойник не может сказать вторую фразу. С другой стороны, три купца также не могут сидеть рядом (иначе средний солгал бы, говоря, что у него есть сосед-разбойник). Значит, среди любых трёх сидящих подряд есть разбойник, т.е. не более двух из них могут сказать вторую фразу. Разбивая сидящих на четыре тройки сидящих подряд, получаем, что не более 4 ⋅ 2 = 8 человек могли сказать вторую фразу. Ровно 8 (купцов) из сидящих за столом могли сказать требуемую фразу, если за столом люди сидят в таком порядке: РККРККРККРКК.
