Maths Olympiad Prep

Library / /7 of 8

Combinatorics Difficulty 6.2 National Olympiad Find the answer Italy

Problem:

On the island that isn't there there are 2008 inhabitants, divided into three clans: the knaves who always lie, the knights who never lie, the pages who lie one day yes and one day no. Lorenza, visiting for two days, meets them all on the first day. The first says: "there is exactly one knave on the island"; the second says: "there are exactly two knaves on the island"... the 2008-th says: "there are exactly 2008 knaves on the island". The following day Lorenza questions them all again in the same order. The first says: "there is exactly one knight on the island"; the second says: "there are exactly two knights on the island"... the last says: "there are exactly 2008 knights on the island".
How many pages are there on the island?

Pick one

Solution

Solution:

The answer is (B). Lorenza notices that both on the first day and on the second day all 2008 inhabitants make conflicting statements, a sign that at least 2007 of them are lying. That is, at most one is telling the truth on the first day, and at most one on the second. From this we deduce that at least 2006 have lied on both days, that is there are at least 2006 knaves, and that in total there is at most one single knight. In fact on the first day exactly one told the truth, because if they had all lied there would be no knaves on the island, contrary to what has already been deduced. On the second day, however, no one could have told the truth, in fact there are no knights. If there were, the only knight would be the first inhabitant, who on the second day said that there is exactly one knight. But this one stated on the first day that there is only one knave, when there are at least 2006. Now we have 2007 liars on the first day and 2008 on the second, hence we deduce that 2007 are knaves and that the single one who told the truth on the first day is a page. (in particular it is exactly the second-to-last inhabitant to have been questioned).

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 translated into English from it; metadata (topic, difficulty) added by this project.