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

Кратко: ответ — 2 шестиместных столика. Пошаговое решение 1) Разберёмся с составом столов по логике костей: - 5-местный стол: у него 5 мест. Что должно быть, чтобы каждый житель на этом столе говорил правду/ложь согласно правилам? - Если на таком столе есть хотя бы один рыцарь, то его высказывание требует, чтобы остальные 4 человека за столом были лжецами. Следовательно, на 5-местном столе не может быть более одного рыцаря — иначе рыцарь увидит за столом другого рыцаря, и условие «не считая меня» для него не выполнится. Поэтому на 5-местном столе может быть ровно 1 рыцарь и 4 лжеца. - Вариант «все лжецы» невозможен, потому что каждый лжец увидит за столом 4 лжеца и его высказывание окажется истинным, что противоречит природе лжеца. Итак, вывод: каждый 5-местный стол имеет exactly 1 рыцаря и 4 лжеца. - 6-местный стол: здесь 6 мест. Пусть за столом сидит k рыцарей (и 6−k лжецов). - Рассмотрим рыцаря: у него за спиной 5 других людей. Чтобы его утверждение было правдой, среди этих 5 должно быть как минимум 4 лжеца. Значит число ложных за столом людей помимо самого рыцаря должно быть не ниже 4, т. е. число рыцарей среди остальных не более 1. Так что при рыцаре на столе общее число рыцарей k должно быть ≤ 2. - Рассмотрим лжеца: его утверждение ложь. Среди остальных 5 должно быть меньше чем 4 лжеца, иначе высказывание оказалось бы истинным. Значит среди остальных должно быть как минимум 2 рыцаря. Это дополнительно ограничивает возможные варианты. Отсюда вместе с первым пунктом получается единственный совместимый вариант: за 6-местным столом exactly 2 рыцаря и 4 лжеца. Итог по составу столов: - 5-местный стол: 1 рыцарь + 4 лжеца. - 6-местный стол: 2 рыцаря + 4 лжеца. 2) Общее число столов и рассадка Пусть a — число 5-местных столов, b — число 6-местных столов. Всего гостей: 5a + 6b = 872. Общее число рыцарей: a*(1) + b*(2) = a + 2b. 3) Найдём минимальное possible число рыцарей (минимизируем a + 2b при условии 5a + 6b = 872) - Рассмотрим 5a + 6b = 872 по модулю 5: 872 ≡ 2 (mod 5), а 6b ≡ b (mod 5). значит b ≡ 2 (mod 5). - Запишем b = 2 + 5t, где t целое неотрицательное. Тогда a = (872 − 6b)/5 = (872 − 6(2 + 5t))/5 = (860 − 30t)/5 = 172 − 6t. - Требуется a ≥ 0, значит t ≤ 28. Следовательно t = 0,1,2,...,28. - Число рыцарей N = a + 2b = (172 − 6t) + 2(2 + 5t) = 176 + 4t. - Это линейная функция по t с положительным коэффициентом 4, поэтому минимум достигается при t = 0. - При t = 0: b = 2, a = 172, N_min = 176. Ответ: минимальное возможное число рыцарей достигается, если заняты ровно 2 шести местных столика. Дополнение: распределение по столам в этом случае: - 172 пяти местных стола (1 рыцарь и 4 лжеца каждый), - 2 шести местных стола (по 2 рыцаря и 4 лжеца каждый). Всего рыцарей: 172*1 + 2*2 = 176, что даёт 872 гостя (176 рыцарей + 696 лжецов).