Problem:
On an island there are two categories of people: knights, who always tell the truth, and knaves, who always lie. On a certain day the grand council convenes, made up of 2003 members. They sit at random around a round table, and during the meeting each of them declares: "Both my neighbors are knaves". The next day the council meets again, but one of the members is sick, so that only 2002 members are present. They arrange themselves again at random around the round table and each of them says: "Both my neighbors belong to the category opposite to mine".
Was the sick member a knave or a knight?
Solution
Solution:
The sick member was a knight.
From the declaration of the first day one deduces that next to every knight there are two knaves, while it is not possible that there are two knaves next to a knave. In particular, there cannot be three consecutive knaves, and therefore, out of 3 people seated consecutively at the table, at least one is a knight. Let us sum the number of occurrences of knights over all 2003 triples of consecutive seats. The total must be at least 2003 and, since in this way every knight is counted 3 times (as many times as the triples of consecutive seats in which he is found), one deduces that the number of knights must be greater than or equal to one third of those present, that is, greater than or equal to 668.
From the declaration of the second day one deduces again that next to every knight there are two knaves, while next to a knave there cannot sit two knights. In all cases, in a triple of consecutive people there can be at most one knight. Similarly to before, one deduces that the number of knights present must be less than or equal to one third of those present, that is, less than or equal to 667.
Therefore the only possibility is that the sick member was a knight. Note finally that, if the sick member was a knight, the situation described is indeed possible: for example, on the first day of the meeting there can be 668 knights and 1335 knaves seated according to the pattern CFFCFF...... CFFCFFCF and on the second day of the meeting there can be 667 knights and 1335 knaves seated according to the pattern CFFCFF......CFFCFFF. Note: to obtain that on the first day the number of knights must be greater than or equal to 668, one can also reason as follows: certainly there is a knight, and to his right there must be a knave. Dividing the remaining 2001 seats into 667 groups of three consecutive ones, one notices that in each of them there must be a knight and therefore the total number of knights must be greater than or equal to 668. Similarly, for the second day one can observe that certainly there is a knave, and dividing the other 2001 seats into 667 groups of 3 consecutive ones, one notices that in each of them there is at most one knight, and therefore the number of knights is less than or equal to 667.
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.