На острове рыцарей и лжецов рыцари всегда говорят правду, а лжецы всегда лгут. На «Празднике середины осени» проводили фуршет. 872 гостя рассадили за 5-местные и 6 -местные…
На острове рыцарей и лжецов рыцари всегда говорят правду, а лжецы всегда лгут. На «Празднике середины осени» проводили фуршет. 872 гостя рассадили за 5-местные и 6 -местные столики, причем пустых мест за столиками не осталось. Когда все расселись, каждый житель написал в своем личном блоге: «Не считая меня, за моим столиком сидит как минимум 4 лжеца». 1. Какое минимальное число рыцарей могло быть среди гостей? 2. Сколько 5-местных столиков было занято при минимально возможном числе рыцарей?3. Сколько 6-местных столиков было занято при минимально возможном числе рыцарей?
Детальное решение
- Анализ высказываний жильцов по столам
Пусть на столе размером 5 мест сидит k knights (рыцарей) и 5−k лжецов.
- Для рыцаря: за его столом, кроме него самого, должно быть как минимум 4 лжеца. Но на столе 5 мест всего, значит для рыцаря на 5-местном столе должно быть именно 4 лжеца вокруг — т.е. на таком столе может быть только 1 рыцарь и 4 лжеца.
- Для лжеца: их утверждение ложно, значит за их столом не может быть 4 или более лжецов среди остальных. Но если на столе 5 мест, и лжецов больше или равно 4 среди остальных, то утверждение лжеца было бы истинным — противоречие. Следовательно на 5-местном столе не может быть 0 лжецов вокруг, и таким образом единственно устойчивое распределение — 1 рыцарь и 4 лжеца.
Пусть на столе размером 6 мест сидит k knights и 6−k лжецов.
- Для рыцаря: за его столом кроме него должно быть не менее 4 лжецов, т.е. среди остальных 5 мест должно быть 4 или 5 лжецов. Это требует, чтобы всего на столе было не более 2 рыцарей (иначе для рыцаря на столе было бы меньше 4 лжецов вокруг).
- Для лжеца: их утверждение ложно, значит среди остальных 5 мест менее чем 4 лжеца, т.е. не больше 3 лжецов вокруг. Это совместимо только с тем, что на столе есть как минимум 2 рыцаря (иначе бы лжец видел слишком много лжецов вокруг).
В итоге единственно совместимое распределение на 6-местном столе: 2 рыцаря и 4 лжеца.
Итого:
- на каждом 5-местном столе: ровно 1 рыцарь и 4 лжеца.
- на каждом 6-местном столе: ровно 2 рыцаря и 4 лжеца.
- Обозначения и уравнения
- Пусть x — число занятых 5-местных столов, y — число занятых 6-местных столов.
- Всего гостей: 5x + 6y = 872.
- Всего рыцарей: на 5-местных столах дают x рыцарей, на 6-местных — 2y рыцарей. Значит K = x + 2y.
- Минимизация количества рыцарей
- По условию: 5x + 6y = 872, x,y≥0, целые.
- Приведем x через y: x = (872 − 6y)/5. Требуется, чтобы 872 − 6y делилось на 5. 872 mod 5 = 2, поэтому 6y mod 5 ≡ y mod 5 должен равняться 2. Значит y ≡ 2 (mod 5). Пусть y = 5t + 2, t ≥ 0. Тогда x = (872 − 6(5t + 2))/5 = (872 − 30t − 12)/5 = 172 − 6t.
- Количество рыцарей K = x + 2y = (172 − 6t) + 2(5t + 2) = 172 − 6t + 10t + 4 = 176 + 4t.
- Чтобы x ≥ 0: 172 − 6t ≥ 0 → t ≤ 28.
- Чтобы y ≥ 0: automatic для t ≥ 0.
- Таким образом K минимально при t = 0:
- t = 0: y = 2, x = 172, K = 176.
Ответ 1: минимальное число рыцарей — 176.
- Параметры при минимальном числе рыцарей
- При t = 0: y = 2 (две 6-местные карты), x = 172 (стоимость 172 пятиместных столов).
Ответ 2: число занятых 5-местных столов при минимальном числе рыцарей — 172.
Ответ 3: число занятых 6-местных столов при минимальном числе рыцарей — 2.
Проверка
- Всего рыцарей: 172 (из 5-местных) + 2·2 = 172 + 4 = 176.
- Всего лжецов: 872 − 176 = 696.
- По столам: 172 столов по 5 мест дают 172 рыцаря и 4·172 = 688 лжецов. 2 столa по 6 мест дают 4 рыцаря и 4 лжеца. Итого: рыцари = 176, лжецы = 688 + 8 = 696. Согласовано.
