Maths Olympiad Prep

Library / /6 of 46

Combinatorics Difficulty 5.1 AIME, harder Prove it Russia

30 persons, each of whom is either a Knight or a Liar, sit around the table (the places around the table are numbered 1,2,,301, 2, \ldots, 30 in the consecutive order). The Knights always tell the truth, while the Liars always lie. Each person has exactly one friend among the others. Moreover, the friend of a Knight is a Liar, and the friend of a Liar is a Knight. Each person was asked the question "Is it true that your friend is a neighbor of you?" Fifteen persons sitting on the places with odd numbers answered "Yes". Find the number of persons that sit on the places with even numbers and also answered "Yes". (S. Agakhanov)

За круглым столом сидят 30 человек — рыцари и лжецы (рыцари всегда говорят правду, а лжецы всегда лгут). Известно, что у каждого из них за этим же столом есть ровно один друг, причем у рыцаря этот друг — лжец, а у лжеца этот друг — рыцарь (дружба всегда взаимна). На вопрос «Сидит ли рядом с вами ваш друг?» сидевшие через одного ответили «да». Сколько из остальных могли также ответить «да»? (Перечислите все варианты и докажите, что других нет.) (С. Агаханов)

Solution

Answer. 00.

Из условия следует, что все сидящие за столом разбиваются на пары друзей; значит, рыцарей и лжецов поровну. Рассмотрим любую пару друзей. Если они сидят рядом, то рыцарь на заданный вопрос ответит «да», а лжец — «нет». Если же они не сидят рядом, то их ответы будут противоположными. В любом случае ровно один из пары друзей даст ответ «да». Значит, при любой рассадке все остальные 15 ответов будут «нет».

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.