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

Цель: понять и подробно объяснить. Имеем a пятиместных столиков и b шестиместных столиков. Всего гостей 872, значит 5a + 6b = 872. А теперь разберём утверждения жителей таблиц. Обозначим на столе размер t (t = 5 или 6) и число рыцарей x на этом столе (следовательно, лжецов L = t − x). Утверждение каждого жителя: «Не считая меня, за моим столиком сидит как минимум 4 лжеца». - Если человек — рыцарь, утверждение истинно. Тогда для рыцаря на столе с L лжецами (за его исключением) должно выполняться L ≥ 4. - Если человек — лжец, утверждение ложно. Тогда для лжеца за его исключением осталось L − 1 лжецов, и должно быть L − 1 < 4, то есть L ≤ 4. Разбираем по типу стола. - Для пятиместого стола (t = 5). Пусть на столе x рыцарей, L = 5 − x. - Если x = 0, все лжецы. Тогда L = 5, и для лжеца L − 1 = 4, утверждение оказалось бы истинным — противоречие. Значит хотя бы один рыцарь. - Если x = 1, L = 4: рыцарь говорит правду (4 ≥ 4), лжецы — L − 1 = 3 < 4, ложь. Всё согласовано. - Если x ≥ 2, L ≤ 3, тогда рыцари бы требовали L ≥ 4 — не выполняется. Значит на пятиместом столе ровно 1 рыцарь и 4 лжеца. - Для шестиместого стола (t = 6). Пусть на столе x рыцарей, L = 6 − x. - Если x = 1, L = 5: рыцарь говорит правду, но у лжеца L − 1 = 4, утверждение оказалось бы истинным — противоречие. Значит x ≠ 1. - Если x = 2, L = 4: рыцарям подходит условие L ≥ 4, лжецам L − 1 = 3 < 4 — ложь. Всё согласовано. - Если x ≥ 3, L ≤ 3: рыцари требуют L ≥ 4 — противоречие. Значит на шестиместном столе ровно 2 рыцаря и 4 лжеца. Итак, на каждом столе фиксировано: - пятиместный стол: 1 рыцарь и 4 лжеца; - шестиместный стол: 2 рыцаря и 4 лжеца. Тогда всего рыцарей K и лжецов L по отношениям a, b: - K = a·1 + b·2 = a + 2b - L = a·4 + b·4 = 4(a + b) - Всего гостей: 872 = K + L = (a + 2b) + 4(a + b) = 5a + 6b (что и дано) Из условия 5a + 6b = 872 следует, что b ≡ 2 (mod 5). Запишем решения в виде: - a = 172 − 6k - b = 5k + 2 где k — неотрицательное целое и a ≥ 0 требует k ≤ 28. Число рыцарей: - K = a + 2b = (172 − 6k) + 2(5k + 2) = 176 + 4k. Чтобы число рыцарей было минимальным, нужно минимизировать k, то есть k = 0. Тогда: - a = 172, b = 2, K = 176. Ответ на вопрос: минимальное число шестиместных столиков, занятых при минимальном количестве рыцарей, равно 2. При этом всего рыцарей будет 176.