Maths Olympiad Prep

Library / /17 of 24

Combinatorics Difficulty 6.9 National Olympiad Prove it Italy

Let nn be an integer greater than or equal to 2. There are nn people in single file, each of whom is either a knave (and always lies) or a knight (and always tells the truth). Every person, except the first, points to one of the people in front of her and declares "This person is a knave" or "This person is a knight". Knowing that there are strictly more knaves than knights, prove that by listening to the declarations it is possible to determine for each of the people whether she is a knave or a knight.

Solution

We will say that two people are of the same type if they are both knights or both knaves, and of different type otherwise.
We note that, if person AA points to person BB and declares her a knight, then AA and BB are of the same type: both knights (if AA tells the truth) or both knaves (if AA lies). Conversely, if AA declares BB a knave, this means that AA is a knight and BB a knave, or AA a knave and BB a knight: AA and BB are of different type.

Let us number the people from 11 to nn according to their order in the line, establishing that person 11 is the one who is furthest ahead (and does not see anyone in front of her). We can now deduce from the declarations, for each person from the second to the nn-th, whether she is or is not of the same type as person number 11; in particular, the declaration of 22 allows us to determine this for 22, the declarations of 22 and 33 together determine it for 33, and thus the declarations of the people from the permanent second to the kk-th determine whether the latter is or is not of the same type as the first. The reason is the following: person 22 necessarily points to the first, and is of her same type if she declares her a knight, of different type otherwise. Person 33 points to 11 or 22: for both of them, thanks to the statement of 22, we know whether their type is the same as 11's, and consequently we can deduce it for 33. We proceed in the same way, in order, up to person nn.

Suppose there are mm people of the type of 11 (person number 11 included) and nmn-m people of the other type. We know that there must be more knaves than knights, so mm will be strictly greater than or strictly less than nmn-m.

In the first case we can deduce that 11 and all the people of her type are knaves, the others knights; conversely in the second case.

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.