На острове рыцарей и лжецов рыцари всегда говорят правду, а лжецы всегда лгут. На «Празднике середины осени» проводили фуршет. 883 гостя рассадили за 5-местные и 6-местные…

Разберём задачу по шагам.

1. Анализ утверждений жителей на столах

• Пусть на столе размером 5 мест сидят k рыцарей и 5 − k лжецов.

  • Если есть хотя бы один рыцарь, то для рыцаря на этом столе остальные четыре места (5−1) должны содержать как минимум 4 лжеца. Это возможно только если остальные четверо — лжецы, то есть на таком столе может быть ровно 1 рыцарь и 4 лжеца.
  • Если бы рыцарей было больше чем 1, то у одного из них среди оставшихся четырёх было бы как минимум ещё одно место под рыцаря, и условие «как минимум 4 лжеца» оказалось бы ложным. Значит, на столе 5 мест может быть либо 1 рыцарь и 4 лжеца, либо невозможно иное сочетание. Но если на столе 5 мест не было бы рыцаря вовсе, то у лжеца утверждение «за моим столиком кроме меня как минимум 4 лжеца» оказалось бы истинным (так как все остальные 4 — лжецы), что недопустимо. Следовательно, на 5-местном столе точно 1 рыцарь и 4 лжеца.

• Пусть на столе размером 6 мест сидят m рыцарей и 6 − m лжецов.

  • Если на столе 6 мест нет рыцаря (m = 0), то любой лжец увидит за соседними местами 5 лжецов, и утверждение «за моим столиком кроме меня как минимум 4 лжца» было бы истинным — противоречие. Значит, m ≥ 1.
  • Если на столе 6 мест ровно 1 рыцарь (m = 1), то у этого рыцаря за соседними местами 5 человек — 5 лжецов, утверждение истинно. Но у каждого лжеца за соседними местами остаются 4 лжеца и 1 рыцарь, следовательно количество лжецов среди остальных 5 равно 4, и их утверждение тоже оказалось бы истинным. Это противоречит тому, что лжецы должны говорить неправду. Значит, m ≠ 1.
  • Если на столе 6 мест ровно 2 рыцаря (m = 2), то у каждого рыцаря среди остальных 5 присутствует 1 рыцарь и 4 лжеца, т. е. там 4 лжеца — утверждение истинно. У каждого лжеца среди остальных 5 — 2 рыцаря и 3 лжеца, т. е. там 3 лжеца — утверждение ложно. Это согласуется с правилами. Значит, на 6-местном столе возможно ровно 2 рыцаря.
  • При m ≥ 3 получить бы у одного из рыцарей не менее 2 рыцарей среди остальных 5, т.е. не менее 3 лжецов — утверждение стало бы ложным. Поэтому таких конфигураций нет.

Итого:

• на каждом 5-местном столе: 1 рыцарь и 4 лжеца.
• на каждом 6-местном столе: 2 рыцаря и 4 лжеца.

2. Система уравнений по rests (количество столиков)

Пусть:

• x — число 5-местных столиков,
• y — число 6-местных столиков.

Условие полного заполнения без пустых мест: 5x + 6y = 883.

Общее число рыцарей: N = 1·x + 2·y = x + 2y.

3. Решение диофрического уравнения и минимизация числа рыцарей

Из 5x + 6y = 883 получаем по стандартной технике mod 6: 5x ≡ 883 (mod 6) → 5x ≡ 1 (mod 6) → x ≡ 5 (mod 6). Пусть x = 6t + 5, t ≥ 0. Подстановка даёт: 5(6t + 5) + 6y = 883 → 30t + 25 + 6y = 883 → 6y = 858 − 30t → y = 143 − 5t.

Требуются неотрицательные x, y: t ≥ 0 и y = 143 − 5t ≥ 0 → t ≤ 28.

Число рыцарей: N = x + 2y = (6t + 5) + 2(143 − 5t) = 291 − 4t. Это выражение убывает с ростом t, значит минимальное N достигается при максимальном t, т. е. t = 28.

Тогда: x = 6·28 + 5 = 173, y = 143 − 5·28 = 3, N = 173 + 2·3 = 179.

Ответ на вопрос задачи: минимальное возможное число рыцарей достигается при размещении 3 шести-местных столиков.

Итак, при минимальном числе рыцарей занято 3 шести-местных столика.