Острове рыцарей и лжецов рыцари всегда говорят правду, а лжецы всегда лгут. На «Празднике середины осени» проводили фуршет. 877 гостей рассадили за 5-местные и 6 -местные столики, причем пустых мест за столиками не осталось. Когда все расселись, каждый житель написал в своем личном блоге: «Не считая меня, за моим столиком сидит как минимум 4 лжеца». 1. Какое минимальное число рыцарей могло быть среди гостей?

Задача сводится к разбору поTables (5-местные и 6-местные) и проверке высказываний рыцарей (правдивы) и лжецов (лгут). 1) Анализ для 5-местного стола - Пусть на таком столе сидит x рыцарей (x может быть 0,1,2,...,5). - Если рыцарь присутствует, в остальных 4 местах должно быть как минимум 4 лжеца, т.е. число лжецов среди остальных равно 4. Это возможно только если на столе всего 1 рыцарь (потому что если бы их было 2 или больше, то среди остальных было бы ≤3 лжецов). Следовательно, если на 5-местном столе есть рыцари, их должно быть ровно один. - Если нет рыцарей (x=0), все 5 людей — лжецы. Но лжецы утверждают «за моим столом, не считая меня, как минимум 4 лжеца». У остальных 4 гостей было бы 4 лжеца — утверждение оказалось бы истинным, что невозможно для лжецов. Значит x ≠ 0. - Итого для 5-местного стола единственно допустимая конфигурация: 1 рыцарь и 4 лжеца. 2) Анализ для 6-местного стола - Пусть на таком столе сидит x рыцарей (x может быть 0,1,2,...,6). - Если на столе есть рыцарь, то среди остальных 5 должны быть как минимум 4 лжеца. Это возможно тогда, когда число лжецов на столе равно 4 или 5, то есть x ≤ 2. - Если на столе есть лжец, то среди остальных 5 лжецов должно быть меньше 4 лжецов, чтобы высказывание лжеца было ложным. Это возможно только если число лжецов на столе ≤ 4, т.е. x ≥ 2. - Единственная совместимая конфигурация для 6-местного стола: 2 рыцаря и 4 лжеца. Итого: - 5-местный стол: точно 1 рыцарь и 4 лжеца. - 6-местный стол: точно 2 рыцаря и 4 лжеца. 3) Общее число столов Пусть a — количество 5-местных столов, b — количество 6-местных столов. Условие заполненности мест: 5a + 6b = 877. Общее число рыцарей N равно: N = 1·a + 2·b = a + 2b. 4) Поиск минимального N Из 5a + 6b = 877 следует, что 877 ≡ 2 (mod 5), и 6b ≡ b (mod 5). Поэтому b ≡ 2 (mod 5). Запишем b = 2 + 5k, где k целое и b ≥ 0. Тогда a = (877 − 6b)/5 = (877 − 12 − 30k)/5 = 173 − 6k. Чтобы a ≥ 0, нужно k ≤ 28. Также k ≥ 0, чтобы b не стал отрицательным. Тогда N = a + 2b = (173 − 6k) + 2(2 + 5k) = 173 − 6k + 4 + 10k = 177 + 4k. Минимум достигается при наименьшем k, то есть k = 0: - b = 2 - a = 173 - N_min = 177 5) Проверка и пример размещения - 173 стола по 5 мест: по 1 рыцарю и 4 лжеца на каждом. - 2 стола по 6 мест: по 2 рыцаря и 4 лжеца на каждом. Всего рыцарей: 173·1 + 2·2 = 173 + 4 = 177. Всего гостей: 5·173 + 6·2 = 865 + 12 = 877. Лжецов: 877 − 177 = 700. Это соответствует сумдам по столам: 173·4 + 2·4 = 692 + 8 = 700. 6) Ответ Минимальное возможное число рыцарей среди гостей — 177.