Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Рассмотрим произвольного рыцаря. Из его фразы следует, что на собрании рыцарей и лжецов. Построим двудольный граф знакомств рыцарей и лжецов, в первой доле вершины — рыцари, во второй — лжецы. Из каждой из хотя бы вершин первой доли исходит минимум ребер, следовательно, ребер в графе C другой стороны, лжец знаком не более, чем с рыцарями, а значит, если лжецов то имеем

Приведем пример на рыцарей и лжецов: пронумеруем рыцарей и лжецов. Рассмотрим первых рыцарей. Пусть среди них рыцари и лжецы с одинаковыми номерами будут не знакомы. А также со сдвигом на один: второй рыцарь не знаком с первым лжецом, третий рыцарь со вторым и так далее. Все остальные знакомы, рыцари попарно знакомы между собой, а лжецы попарно не знакомы. Такая ситуация подходит, так как каждый лжец не знаком хотя бы с двумя рыцарями, и каждый рыцарь знаком хотя бы с лжецами.