Maths Olympiad Prep

Track / Stage 5 / 378 of 400 #978 of 1964

Problem 978

AIME late
Combinatorics Difficulty 5.9 Prove it

5. On an island, there live only knights, who always tell the truth, and liars, who always lie. One day, they all sat in a circle, and each one said: "Among my two neighbors, there is a liar!" Then they sat in a circle in a different order, and each one said: "Among my two neighbors, there is no knight!" Could there have been 2017 people on the island? (L. Samoilov)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Answer. It could not. Solution. In the first round, both neighbors of each liar were knights. By matching each liar with their right neighbor in this round, we can be convinced that there are no fewer knights than liars on the island. In the second round, both neighbors of each knight were liars. By matching each knight with their right neighbor in this round, we can be convinced that there are no more knights than liars on the island. It turns out that there are an equal number of knights and liars on the island. But then the number of inhabitants on the island is even, while the number 2017 is odd.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.