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

Детальное решение 1) Анализ высказываний жильцов по столам - Пусть на столе размером 5 мест сидит k knights (рыцарей) и 5−k лжецов. - Для рыцаря: за его столом, кроме него самого, должно быть как минимум 4 лжеца. Но на столе 5 мест всего, значит для рыцаря на 5-местном столе должно быть именно 4 лжеца вокруг — т.е. на таком столе может быть только 1 рыцарь и 4 лжеца. - Для лжеца: их утверждение ложно, значит за их столом не может быть 4 или более лжецов среди остальных. Но если на столе 5 мест, и лжецов больше или равно 4 среди остальных, то утверждение лжеца было бы истинным — противоречие. Следовательно на 5-местном столе не может быть 0 лжецов вокруг, и таким образом единственно устойчивое распределение — 1 рыцарь и 4 лжеца. - Пусть на столе размером 6 мест сидит k knights и 6−k лжецов. - Для рыцаря: за его столом кроме него должно быть не менее 4 лжецов, т.е. среди остальных 5 мест должно быть 4 или 5 лжецов. Это требует, чтобы всего на столе было не более 2 рыцарей (иначе для рыцаря на столе было бы меньше 4 лжецов вокруг). - Для лжеца: их утверждение ложно, значит среди остальных 5 мест менее чем 4 лжеца, т.е. не больше 3 лжецов вокруг. Это совместимо только с тем, что на столе есть как минимум 2 рыцаря (иначе бы лжец видел слишком много лжецов вокруг). В итоге единственно совместимое распределение на 6-местном столе: 2 рыцаря и 4 лжеца. Итого: - на каждом 5-местном столе: ровно 1 рыцарь и 4 лжеца. - на каждом 6-местном столе: ровно 2 рыцаря и 4 лжеца. 2) Обозначения и уравнения - Пусть x — число занятых 5-местных столов, y — число занятых 6-местных столов. - Всего гостей: 5x + 6y = 872. - Всего рыцарей: на 5-местных столах дают x рыцарей, на 6-местных — 2y рыцарей. Значит K = x + 2y. 3) Минимизация количества рыцарей - По условию: 5x + 6y = 872, x,y≥0, целые. - Приведем x через y: x = (872 − 6y)/5. Требуется, чтобы 872 − 6y делилось на 5. 872 mod 5 = 2, поэтому 6y mod 5 ≡ y mod 5 должен равняться 2. Значит y ≡ 2 (mod 5). Пусть y = 5t + 2, t ≥ 0. Тогда x = (872 − 6(5t + 2))/5 = (872 − 30t − 12)/5 = 172 − 6t. - Количество рыцарей K = x + 2y = (172 − 6t) + 2(5t + 2) = 172 − 6t + 10t + 4 = 176 + 4t. - Чтобы x ≥ 0: 172 − 6t ≥ 0 → t ≤ 28. - Чтобы y ≥ 0: automatic для t ≥ 0. - Таким образом K минимально при t = 0: - t = 0: y = 2, x = 172, K = 176. Ответ 1: минимальное число рыцарей — 176. 4) Параметры при минимальном числе рыцарей - При t = 0: y = 2 (две 6-местные карты), x = 172 (стоимость 172 пятиместных столов). Ответ 2: число занятых 5-местных столов при минимальном числе рыцарей — 172. Ответ 3: число занятых 6-местных столов при минимальном числе рыцарей — 2. Проверка - Всего рыцарей: 172 (из 5-местных) + 2·2 = 172 + 4 = 176. - Всего лжецов: 872 − 176 = 696. - По столам: 172 столов по 5 мест дают 172 рыцаря и 4·172 = 688 лжецов. 2 столa по 6 мест дают 4 рыцаря и 4 лжеца. Итого: рыцари = 176, лжецы = 688 + 8 = 696. Согласовано.