Some manors of Lipshire county are connected by roads. The inhabitants of manors connected by a road are called neighbours. Is it always possible to settle in each manor a knight (who always tells truth) or a liar (who always lies) so that every inhabitant can say ”The number of liars among my neighbours is at least twice the number of knights”?
Problem
Source: Tuymaada 2021/J4
Tags: combinatorics
01.07.2023 19:56
Sure, we can. Let us settle gentlemen in the manors so that the sum of the number of pairs of neighboring liars and twice the number of pairs of neighboring knights is minimal, and among all the ways to do that we choose one in which the number of pairs of neighboring knights is maximal. Suppose that this arrangement does not satisfy the condition. Two cases are possible: $(1)$ There is a liar telling the truth. Let $l$ be the number of his lying neighbors and $k$ the number of his neighbors-knights. Then $l > 2k.$ Replace this liar by a knight. Then the number of pairs of neighboring liars decreases by $l,$ twice the number of pairs of neighboring knights increases by $2k,$ that is, the sum does not increase. But the number of pairs of neighboring knights increases, that is, the initial arrangement was not optimal, a contradiction. $(2)$ There is a lying knight. Let $l$ be the number of his lying neighbors and k the number of his neighbors-knights, $l < 2k.$ Similarly to $(1),$ we can replace this knight by a liar. Then the number of pairs of neighboring liars increases by $l,$ twice the number of pairs of neighboring knights decreases by $2k,$ and their sum decreases. This is again a contradiction with the choice of the arrangement. So we are done.