Let be an integer greater than or equal to 2. There are 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 points to person and declares her a knight, then and are of the same type: both knights (if tells the truth) or both knaves (if lies). Conversely, if declares a knave, this means that is a knight and a knave, or a knave and a knight: and are of different type.
Let us number the people from to according to their order in the line, establishing that person 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 -th, whether she is or is not of the same type as person number ; in particular, the declaration of allows us to determine this for , the declarations of and together determine it for , and thus the declarations of the people from the permanent second to the -th determine whether the latter is or is not of the same type as the first. The reason is the following: person necessarily points to the first, and is of her same type if she declares her a knight, of different type otherwise. Person points to or : for both of them, thanks to the statement of , we know whether their type is the same as 's, and consequently we can deduce it for . We proceed in the same way, in order, up to person .
Suppose there are people of the type of (person number included) and people of the other type. We know that there must be more knaves than knights, so will be strictly greater than or strictly less than .
In the first case we can deduce that and all the people of her type are knaves, the others knights; conversely in the second case.