На острове рыцарей и лжецов рыцари всегда говорят правду, а лжецы всегда лгут. На «Празднике середины осени» проводили фуршет. гостей рассадили за -местные и -местные столики,…
На острове рыцарей и лжецов рыцари всегда говорят правду, а лжецы всегда лгут. На «Празднике середины осени» проводили фуршет. гостей рассадили за -местные и -местные столики, причем пустых мест за столиками не осталось. Когда все расселись, каждый житель написал в своем личном блоге: «Не считая меня, за моим столиком сидит как минимум лжеца». Какое минимальное число рыцарей могло быть среди гостей? Введите целое число или десятичную дробь… За этот вопрос вы можете получить 3 балла Сколько -местных столиков было занято при минимально возможном числе рыцарей? Введите целое число или десятичную дробь… За этот вопрос вы можете получить 1 балл Сколько -местных столиков было занято при минимально возможном числе рыцарей? Введите целое число или десятичную дробь… За этот вопрос вы можете получить 1 балл
Предмет: логика/ combinatorics (рыцари и лжецы); Тип задач: разбор условий рассадки и логика утверждений.
Допущение: на празднике стоят только 4-местные и 6-местные столики; все места заняты; ни одного пустого места.
Пусть x — число 4-местных столиков, y — число 6-местных столиков. Тогда на каждом столике ровно один лжец и остальные — рыцари.
Почему именно так:
- Если на столике вообще не было бы лжеца, то любой рыцарь на этом столике сообщил бы, что рядом есть лжец, что было бы ложью, следовательно противоречие. Значит на каждом столике есть хотя бы один лжец.
- Но если на столике было бы два и более лжецов, то каждый лжец увидел бы как минимум еще одного лжеца рядом и его утверждение «за моим столиком стоит как минимум один лжец» оказалось бы правдой, что противоречит тому, что лжец должен лгать. Значит на столике не может быть более одного лжца.
- Следовательно, на каждом столике ровно один лжец, а остальные — рыцари.
Соответственно:
- на 4-местном столике: 1 лжец и 3 рыцаря;
- на 6-местном столике: 1 лжец и 5 рыцарей.
Общее число рыцарей: N = 3x + 5y. Общее число лжецов равно числу столиков: L = x + y.
Задача минимизировать число рыцарей. Это минимизирует выражение 3x + 5y при x, y≥0 и не оба нуля.
- При x = 1, y = 0 получаем N = 3 (минимальное возможное).
- Любое другое сочетание даёт N ≥ 5 (например, x = 0, y = 1 даёт N = 5).
Ответы:
- Минимальное число рыцарей: 3
- Сколько 4-местных столиков занято при минимальном числе рыцарей: 1
- Сколько 6-местных столиков занято при минимальном числе рыцарей: 0
Итоговые числа: 3; 1; 0.
