Задача 2. Рыцари и лжецы в ряд

Сколько людей слева

Фраза человека говорит о том, сколько людей стоит слева от него, поэтому сначала разберёмся с местами в ряду.

Слева от крайнего левого человека нет никого — $0$ человек, а $0$ — чётное число. Слева от второго — $1$ человек, от третьего — $2$, и так далее до крайнего правого: слева от него $23$ человека.

Назовём место Ч-местом, если слева от него чётное число людей ($0,\,2,\,4,\,\ldots,\,22$), и Н-местом, если нечётное ($1,\,3,\,\ldots,\,23$). Чётные и нечётные числа чередуются, поэтому Ч- и Н-места идут через одно: в ряду $12$ Ч-мест и $12$ Н-мест.

Кто какую фразу говорит

Будем называть фразы коротко: «чётное» — это «Слева от меня чётное число человек», «нечётное» — «Слева от меня нечётное число человек».

На Ч-месте правдива фраза «чётное», на Н-месте — «нечётное». Рыцарь говорит правду, лжец — неправду. Получаются четыре случая:

• рыцарь на Ч-месте говорит «чётное»;
• рыцарь на Н-месте говорит «нечётное»;
• лжец на Ч-месте говорит «нечётное»;
• лжец на Н-месте говорит «чётное».

Значит, фразу «чётное» произносят рыцари на Ч-местах и лжецы на Н-местах, а все остальные произносят «нечётное».

Как до этого догадаться: фраза человека зависит только от двух вещей — кто он и на каком месте стоит. Поэтому удобно разложить всех $24$ человек по четырём клеткам таблицы «рыцарь или лжец» × «Ч-место или Н-место».

Две равные группы

Пусть на Ч-местах стоят $a$ рыцарей. Всего Ч-мест $12$, значит, остальные $12-a$ человек на Ч-местах — лжецы. Всего лжецов тоже $12$; на Ч-местах их $12-a$, значит, на Н-местах стоят

лжецов.

Получилось: лжецов на Н-местах ровно столько же, сколько рыцарей на Ч-местах. Посмотри на таблицу под этим шагом: число $12$ здесь участвует дважды — Ч-мест $12$ и лжецов $12$. В обоих числах есть одна и та же часть — лжецы на Ч-местах. Если убрать её из обоих, останутся равные части: рыцари на Ч-местах и лжецы на Н-местах.

Считаем фразы

Фразу «чётное» сказали рыцари на Ч-местах и лжецы на Н-местах, то есть

человек — это чётное число. Фразу «нечётное» сказали остальные $24-2a$ человек — тоже чётное число.

А $17$ и $7$ — нечётные числа. Значит, ни $17$ «чётных» и $7$ «нечётных» фраз, ни наоборот получиться не могло.

Ответ: не могло.

Где пригодились «12 и 12»

В шаге 3 мы воспользовались тем, что лжецов столько же, сколько Ч-мест. Без этого рассуждение ломается — и ответ тоже. Например, если бы в ряду стояли $13$ рыцарей и $11$ лжецов, могло бы получиться $17$ и $7$: поставим на Ч-места $9$ рыцарей и $3$ лжецов, а на Н-места — $4$ рыцарей и $8$ лжецов. Тогда «чётное» скажут $9+8=17$ человек, а «нечётное» — $4+3=7$.

Так что ответ «не могло» держится именно на равенстве: в условии лжецов $12$ и Ч-мест $12$. В модели можно сделать лжецами $11$ человек и проверить это самому.

Второй вариант

Рассуждение то же, только людей считаем справа и числа другие. Если идти по ряду слева направо, то справа от людей стоят $19,\,18,\,\ldots,\,1,\,0$ человек: у крайнего правого справа никого нет, а $0$ — чётное число. Ч-места — где справа чётное число людей, Н-места — где нечётное; они идут через одно, тех и других по $10$.

Фразу «Справа от меня чётное число человек» (коротко — «чётное») говорят рыцари на Ч-местах и лжецы на Н-местах. Пусть рыцарей на Ч-местах $b$. Тогда лжецов на Ч-местах $10-b$, а на Н-местах

лжецов — снова потому, что Ч-мест столько же, сколько лжецов: по $10$.

Значит, «чётное» сказали $b+b=2b$ человек, а «нечётное» — $20-2b$: оба числа чётные. А $13$ и $7$ — нечётные, поэтому так быть не могло. Перебор всех $184\,756$ рядов это подтверждает.

Ответ: не могло.