Задачка про умных и дураков.

Итак, решение, как обещал. Так как хотел бы сделать все максимально понятно, будет длинно.

Перефразируем задачу, чтобы решение было понятнее. Есть ведущий, есть умные и дураки, всего 30, дураков F. Дураки могут придумывать рассадки и свои ответы в этих рассадках так, чтобы запутать ведущего - чтобы он не смог указать точно на умного. Например, если F=15, сделать это легко - дураки садятся через одного, и всегда говорят Д. Ведущий услышит 30 ответов Д, и уверенно выбрать умного не получится.

На рисунках будем обозначать + умного, - дурак, а звания, которыми их наградили соседи слева, буквами У и Д соответственно.

Пусть ведущий уверен, что в в рассадке есть N подряд умных. Тогда ведущий услышит хотя бы раз как минимум N-1 ответов У подряд. Например при N=3:

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

Отсюда промежуточная лемма: если ведущий уверен, что в рассадке есть N подряд умных, дуракам нужно выделить не менее N дураков подряд, чтобы запутать ведущего.

Теперь докажем, что при F = 8 у дураков это не получится.

При F = 8 точно будет как минимум три умных подряд (легко проверить, что при двух умных подряд не получится). Это значит, что дуракам (исходя из леммы) необходимо выделить три дурака подряд, чтобы запутать ведущего. Но тогда останется 30 - 3 = 27 игроков, из которых 8 - 3 = 5 дураков и 22 умных. Как бы не распределялись оставшиеся дураки, в этом случае обязательно найдется 4 умных подряд.

Но если есть 4 умных подряд, то дуракам придется выделить 4 дурака подряд, чтобы запутать ведущего. 30 - 4 = 26, из которых остается 4 дурака и 22 умных. Как бы не не распределялись оставшиеся дураки, в этом случае обязательно найдется 5 умных подряд.

Аналогично дальше. В результате получается, что при F= 8 ведущий всегда может выбрать самую длинную последовательность из ответов У, и последний У точно укажет на умного.

То есть при F=8 ведущий точно сможет указать умного. Алгоритм такой: он берет самую длинную последовательность из У, выбирает последний У в такой последовательности, и объявляет его умным.

Таким образом, было доказано, что при F=8 у дураков не получится обмануть ведущего. А при F=9 они справятся, вот пример:

Какую бы позицию ведущий не выбрал, она може оказаться и + и -