7.4. За круглый стол переговоров сели гномы и эльфы: суммарно 1001 участник, причём все разного возраста. Известно, что эльфы всегда лгут, а гномы всегда говорят правду. Каждому из участников переговоров был задан вопрос «У тебя есть сосед-эльф младше тебя?», на который все ответили «Да». После этого переговорщики пошли на перерыв, а вернувшись, сели за стол в случайном порядке. На этот раз каждому из участников был задан вопрос «У тебя есть сосед-гном младше тебя?». Докажите, что хотя бы двое ответили «Да».

В первом рассаживании рядом не могли сидеть два эльфа: младший из них имел бы соседа-эльфа младше себя? Нет — младший не имел бы такого соседа, поэтому, сказав «Да», сказал бы правду, что противоречит тому, что эльфы лгут. Следовательно, эльфы не соседствовали друг с другом.

Второе рассаживание рассмотрим как круговую последовательность участников. Назовём гнома «дающим ответ “Да”», если рядом с ним есть гном младше него. Эльф отвечает «Да» тогда и только тогда, когда рядом с ним нет гнома младше него.

Используем факт о круговой последовательности с попеременно обозначенными типами на участках: если среди участников нет соседних эльфов и каждый гном в исходном порядке имел рядом младшего эльфа, то при любом новом круговом порядке найдутся либо два гнома, каждый из которых соседствует с младшим гномом, либо два эльфа, каждый из которых не соседствует с младшим гномом. Это следует, если пройти по кругу и сравнивать соседние возраста: при переходе от «есть младший сосед того же типа» к «нет младшего соседа того же типа» число переходов между состояниями на замкнутом круге чётно; условие исходного порядка исключает возможность оставить только один участник каждого подходящего типа.

В первом случае эти два гнома правдиво отвечают «Да». Во втором случае оба эльфа лгут и также отвечают «Да». Значит, в любом случае утвердительных ответов не меньше двух.