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

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

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

Пусть x — число занятых 5-местных столов, y — число занятых 6-местных столов. Тогда:

• 5x + 6y = 888 (всего мест заполнено).
• Количество рыцарей K = x + 2y.

Разложим решение по диофееву уравнению 5x + 6y = 888:

• По модулю 6: 5x ≡ 888 ≡ 0 (mod 6) ⇒ x ≡ 0 (mod 6). Пусть x = 6t.
• Подстановка дает: 30t + 6y = 888 ⇒ 5t + y = 148 ⇒ y = 148 − 5t.
• Требуются x ≥ 0, y ≥ 0 ⇒ t ∈ {0, 1, …, 29}.

Тогда число рыцарей:

• K = x + 2y = 6t + 2(148 − 5t) = 296 − 4t.

Минимум K достигается при максимальном t, т. е. t = 29. Тогда:

• x = 6t = 174; y = 148 − 5t = 3.
• K = 296 − 4·29 = 296 − 116 = 180.

Проверка: 5·174 + 6·3 = 870 + 18 = 888, верно. Рыцарей: 174 + 2·3 = 180; Лжецов: 888 − 180 = 708, что равно 4(x + y) = 4·177 = 708. Всё согласовано.

Ответы:

1. Минимальное возможное число рыцарей: 180.
2. При минимальном числе рыцарей занятых 5-местных столов: 174.