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

Задача решается пошагово, учитывая логику рыцарей и лжецов и размещение за столами. 1) Анализ по каждому типу стола - 5-местный стол (всего 5 мест, поэтому «не считая меня» — 4 человека): - Если за столом сидит рыцарь, то он говорит правду: остальные 4 за столом — лжецы. Это допустимо. - Если за столом сидит лжец, его высказывание ложно: среди остальных 4 человек не все являются лжецами, то есть среди них есть как минимум один рыцарь. Но тогда у стола оказалось бы более одного рыцаря, что при данном утверждении лжеца может противоречить условию (разбор ниже покажет, что на таком столе нельзя иметь 0 рыцарей и нельзя иметь более чем 1 рыцаря одновременно). - Вывод: на 5-местном столе оптимальная и единственно допустимая конфигурация — ровно 1 рыцарь и 4 лжеца. - 6-местный стол (всего 6 мест, «не считая меня» — 5 человек): - Если за столом нет рыцаря (0 рыцарей): любой лжец скажет правду? его высказывание было бы about 5 других — все лжецы, значит «как минимум 4 лжыца» истинно, но лжец не может говорить правду. Это противоречие, значит 0 рыцарей нельзя. - Если за столом 1 рыцарь: остальные 5 — все лжецы. Рыцарь скажет правду (есть 5 лжецов среди остальных — это “как минимум 4”), но лжецы среди остальных увидят, что среди остальных есть 1 рыцарь и 4 лжеца; число лжецов среди остальных равно 4, значит их утверждение было бы истинно — несовместимо с тем, что они лжецы. Поэтому конфигурация с 1 рыцарём на столе невозможна. - Если за столом 2 рыцаря: остальные 5 человек содержат 2 рыцаря и 3 лжеца. Рыцарь видит среди остальных 4 лжеца? Нет: среди остальных 5 (у одного рыцаря) окажется 4 лжеца и 1 рыцарь — то есть 4 лжеца, следовательно утверждение «как минимум 4 лжеца» истинно. Так же для второго рыцаря. Лжецы видят среди остальных 5 двоих рыцарей и троих лжецов — среди остальных лжецов всего 3, т.е. меньше 4; их утверждение ложно. Совпадает: рыцари говорят правду, лжецы лгут. Значит на 6-местном столе может быть ровно 2 рыцаря и 4 лжеца. - Конфигурации с 3 и более рыцарями на 6-местном столе приводят к противоречию (у рыцарей утверждение не может быть истинным, если рядом больше одного рыцаря), поэтому такие варианты исключаются. - Итак, на 6-местном столе допустимо только 2 рыцаря и 4 лжеца. Итог по столам: - 5-местный стол: ровно 1 рыцарь и 4 лжеца. - 6-местный стол: ровно 2 рыцаря и 4 лжеца. 2) Общее число гостей и минимальное число рыцарей Пусть x — число занятых 5-местных столиков, y — число занятых 6-местных столиков. Тогда: - Условия размещения: 5x + 6y = 872 (потому что все места заняты). - Общее количество рыцарей K равно: каждый 5-местный стол приносит 1 рыцаря, каждый 6-местный — 2 рыцаря, поэтому K = x + 2y. Найдем все целые решения 5x + 6y = 872. По модулю 5 имеем 872 ≡ 2 (мод 5), а 6y ≡ y (мод 5), поэтому 2 - y ≡ 0 (мод 5) => y ≡ 2 (мод 5). Запишем y = 2 + 5t, где t ≥ 0. Тогда x = (872 - 6y)/5 = (872 - 6(2 + 5t))/5 = (860 - 30t)/5 = 172 - 6t. Тогда число рыцарей: K = x + 2y = (172 - 6t) + 2(2 + 5t) = 172 - 6t + 4 + 10t = 176 + 4t. Чтобы минимизировать K, нужно минимизировать t (t ≥ 0). При t = 0 имеем: - x = 172, y = 2, K = 176. Проверка: 5x + 6y = 5·172 + 6·2 = 860 + 12 = 872, всё размещено. 3) Ответы 1) Минимальное возможное число рыцарей: 176. 2) При минимально возможном числе рыцарей занято 5-местных столиков: 172 стола. 3) При минимально возможном числе рыцарей занято 6-местных столиков: 2 стола.