Острове рыцарей и лжецов рыцари всегда говорят правду, а лжецы всегда лгут. На «Празднике середины осени» проводили фуршет. 877 гостей рассадили за 5-местные и 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.