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