Дураки и умные

Rasool · 19.11.2010, 23:42

Нашел такую задачку в "Кванте":

Цитата:

За круглым столом сидит компания из тридцати человек. Каждый их них либо дурак, либо умный. Всех сидящих спрашивают: "Кто ваш сосед справа - умный или дурак?" В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превышает F. При каком наибольшем F всегда можно, зная эти ответы, указать на умного человека в компании?

Не подскажите, какой подход к решению тут нужен? Я в ответе подсмотрел, что сначала людей нужно разбить на чередующиеся группы дураков и умных - всего 2k групп. А дальше что?
Просьба не выкладывать ссылку из Кванта (ответ я могу посмотреть сам), а подсказать ход решения.
Крайние варианты легко определяются: если за столом 1 дурак, то его легко вычислить, если 29 дураков, то очевидно, что умных вычислить невозможно.

venco · 19.11.2010, 23:47

(Оффтоп)

Rasool в сообщении #377612 писал(а):

В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.

Сомнительное утверждение. ;-)

Я бы по старинке "лжецов" использовал.

-- Пт ноя 19, 2010 15:51:42 --

Наверно, надо рассмотретрь вариант, когда все "дураки" изображают из себя "умных", только считают "умными" себя ("дураков"), а настоящих "умных" считают "дураками". Т.е. у нас есть две симметричные группы, и если они одинакового размера, то отличить их друг от друга совершенно невозможно.

Rasool · 20.11.2010, 01:18

venco в сообщении #377613 писал(а):