Олимпиада Туймаада по математике. Младшая лига. 2021 год

В деревне некоторые пары домов соединены дорогами. Жильцы домов, соединённых дорогой, называются соседями. Всегда ли в каждый из этих домов можно поселить рыцаря, который всегда говорит правду, либо лжеца, который всегда лжёт, чтобы каждый житель смог сказать фразу «среди моих соседей лжецов хотя бы вдвое больше, чем рыцарей»? ( С. Берлов )

Комментарий/решение

Давайте поселим жильцов так, чтобы сумма количества пар соседей-лжецов и удвоенного количества пар соседей-рыцарей была минимальна, а среди всех рассадок, для которых достигается этот минимум, выберем ту, в которой количество пар соседей-рыцарей было максимально. Предположим, что при такой рассадке условие задачи не выполняется.

Разберем два случая:

1) Нашелся лжец, который говорит правду. Пусть у него $ℓ$ соседей-лжецов и $k$ соседей-рыцарей, тогда $ℓ\geq2k$. Попробуем вместо этого лжеца поселить рыцаря. Тогда количество пар соседей-лжецов уменьшится на $ℓ$, удвоенное количество пар соседей-рыцарей увеличится на $2k$, и в силу неравенства $ℓ\geq2k$ сумма этих количеств не увеличится. Но при этом увеличится количество пар соседей-рыцарей. Следовательно, изначально мы выбрали не оптимальную рассадку. Противоречие.

2) Нашелся рыцарь, который лжет. Пусть у него $ℓ$ соседей-лжецов и $k$ соседей-рыцарей, $ℓ<2k$. Аналогично попробуем заменить этого рыцаря на лжеца. Тогда количество пар соседей-лжецов увеличится на $ℓ$, удвоенное количество пар соседей-рыцарей уменьшится на $2k$, и в силу неравенства $ℓ<2k$ сумма этих количеств уменьшится. Снова противоречие с выбором оптимальной рассадки.

Таким образом, в выбранной нами рассадке все условия выполняются/