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

Решение задачи 1) Обозначения - Пусть у нас есть a пятиместных столиков и b столиков на 6 мест. - Всего гостей: 5a + 6b = 877. 2) Анализ утверждений «на моём столе вокруг меня не считая меня сидит как минимум 4 лжеца» Пусть на конкретном столе t рыцарей и l лжецов (l = число лжецов за этим столиком, всего за столом). Тогда: - Рыцари говорят правду: для рыцаря число лжецов вокруг него равно l, значит l ≥ 4. - Лжецы лгут: для лжеца число лжецов вокруг него равно l − 1, и утверждение «как минимум 4 лжеца» должно быть ложным, значит l − 1 < 4, т.е. l ≤ 4. Из двух условий следует l = 4. Значит на любом занятом столике должно быть ровно 4 лжеца: - на пятиместном столике (s = 5): всего лжецов l = 4, значит рыцарей t = 1. - на шестиместном столике (s = 6): l = 4, значит рыцарей t = 2. Иными словами: - каждый занятый 5-местный столик: 1 рыцарь и 4 лжеца; - каждый занятый 6-местный столик: 2 рыцаря и 4 лжеца. 3) Система уравнений - 5a + 6b = 877 - число рыцарей K = a · 1 + b · 2 = a + 2b. 4) Решение диофантного уравнения Из 5a + 6b = 877 по модулю 6 получаем: 5a ≡ 1 (mod 6) → −a ≡ 1 (mod 6) → a ≡ 5 (mod 6). Пусть a = 6t + 5 (t ≥ 0). Тогда подстановка даёт 5(6t + 5) + 6b = 877 → 30t + 25 + 6b = 877 → 6b = 852 − 30t → b = 142 − 5t. Условие b ≥ 0 даёт t ≤ 28. Следовательно t = 0,1,2,…,28. 5) Число рыцарей и минимизация K = a + 2b = (6t + 5) + 2(142 − 5t) = 289 − 4t. Чтобы минимизировать K, нужно максимизировать t. Максимум t = 28: - a = 6·28 + 5 = 173 - b = 142 − 5·28 = 142 − 140 = 2 - K = 289 − 4·28 = 177 6) Ответ При минимальном числе рыцарей (177), заняты следующие столики: - пятиместных: a = 173 - шестиместных: b = 2 Следовательно, сколько пятиместных столиков было занято при минимальном числе рыцарей? 173.