Вопрос школьника
В сенате страны рыцарей и лжецов – 100 сенаторов. Каждый из них либо рыцарь, либо лжец. Известно, что:
1) по крайней мере, один из сенаторов – рыцарь;
2) из двух произвольно выбранных сенаторов, по крайней мере, один – лжец.
Определите, сколько в сенате рыцарей и сколько лжецов?
Ответ от учителя
Пусть в сенате $x$ рыцарей и $y$ лжецов. Тогда из первого условия следует, что $xgeq 1$, а из второго условия следует, что $ygeq 1$.
Рассмотрим двух произвольно выбранных сенаторов. Если оба они рыцари, то оба говорят правду. Если оба они лжецы, то оба лгут. Если один из них рыцарь, а другой лжец, то первый говорит правду, а второй лжет. Таким образом, если из двух произвольно выбранных сенаторов по крайней мере один лжец, то оба они не могут быть рыцарями.
Предположим, что $x=1$, то есть в сенате есть только один рыцарь. Тогда из второго условия следует, что среди оставшихся $99$ сенаторов должен быть хотя бы один лжец. Но это противоречит тому, что все они являются рыцарями, кроме одного. Значит, $xgeq 2$.
Предположим, что $y=1$, то есть в сенате есть только один лжец. Тогда из первого условия следует, что среди оставшихся $99$ сенаторов все являются рыцарями. Но это противоречит тому, что по крайней мере один из них лжец. Значит, $ygeq 2$.
Таким образом, мы получили систему неравенств:
$$
begin{cases}
xgeq 1 \
ygeq 1 \
xgeq 2y-1 \
ygeq 2x-99
end{cases}
$$
Первые два неравенства следуют из условия задачи. Третье неравенство следует из того, что если из двух произвольно выбранных сенаторов по крайней мере один лжец, то оба они не могут быть рыцарями. Четвертое неравенство следует из того, что если из двух произвольно выбранных сенаторов по крайней мере один рыцарь, то оба они не могут быть лжецами.
Решая эту систему неравенств, получаем $x=67$ и $y=34$. Значит, в сенате 67 рыцарей и 34 лжеца.
