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

Краткое решение задачи: Цель: минимизировать число рыцарей (knights) при условии, что все гости разместились за 5-местными и 6-местными столами. 1) Разбор по таблицам - 5-местный стол: если на таком столе есть рыцарь, то остальные 4 человека должны быть лжецами (чтобы их заявление «за моим столиком не считая меня как минимум 4 лжеца» было правдивым для рыцаря). Это возможно только при 1 рыцаре и 4 лжецах на столе. Никаких других вариантов (например, 0 или более 1 рыцаря на 5 местах) невозможны. - 6-местный стол: возможны варианты с 0, 1, 2 рыцарями, но анализ показывает: - 0 рыцарей невозможно: у лжецов среди остальных 5 лиц окажется не менее 4 лживых, т.е. их высказывание оказалось бы правдой — противоречие. - 1 рыцарь невозможно: у лжецов остальных 5 лиц будет 4 лжеца и 1 рыцарь; у лжеца станет видна истинность утверждения, что невозможно. - 2 рыцаря возможно: у каждого рыцаря в others остаётся 4 лжеца, что обеспечивает истинность их утверждения; у лжецов остальных 5 лиц (2 рыцаря и 3 лжеца) — число лжецов среди них равно 3, утверждение лжеца ложно — всё согласуется. Значит на 6-местном столе обязательно должно быть ровно 2 рыцаря и 4 лжеца. Итого: - на каждом 5-местном столе: 1 рыцарь и 4 лжеца. - на каждом 6-местном столе: 2 рыцаря и 4 лжеца. Каждый стол имеет ровно 4 лжеца вокруг себя. 2) Разobрали условие про количество столов Пусть a — число 5-местных столов, b — число 6-местных столов. Тогда общее число гостей 877 даёт: 5a + 6b = 877. 3) Найдем допустимые пары (a, b) и минимизируем число рыцарей Всего рыцарей: на 5-местных столах по 1 рыцарю каждый, на 6-местных по 2 рыцаря каждый: K = a + 2b. Из равенства 5a + 6b = 877 получаем a = (877 - 6b)/5, поэтому b должен удовлетворять 877 - 6b ≡ 0 (mod 5). Так как 877 ≡ 2 (mod 5) и 6 ≡ 1 (mod 5), имеем b ≡ 2 (mod 5). Значит возможны b = 2, 7, 12, ..., до максимума, пока a не станет неотрицательным. Ключевой факт: K = a + 2b = (877 - 6b)/5 + 2b = (877 + 4b)/5. Эта величина возрастает с ростом b, поэтому минимальное число рыцарей достигается при минимальном допустимом b, то есть при b = 2. 4) Расчёты при b = 2 - a = (877 - 6·2)/5 = (877 - 12)/5 = 865/5 = 173. - Зеленым образом проверяем: 5a + 6b = 5·173 + 6·2 = 865 + 12 = 877 ✓. - Число рыцарей: K = a + 2b = 173 + 4 = 177. - Общее число столов: T = a + b = 173 + 2 = 175. - Общее число лжецов: 4T = 4·175 = 700. - Сумма: 700 лжецов + 177 рыцарей = 877 гостей ✓. Ответ на вопрос: минимально возможное число занятых 6-местных столиков равно 2.