CombinatoricsDifficulty 5.9AIME, harderFind the answerItaly
Problem:
In the village of Asip all the inhabitants belong to one of the following two groups: the Knights, who always tell the truth, and the Knaves, who always lie. Today, for the annual census, the Grand Notary has arrived from the capital and all the inhabitants line up in single file in front of him. Each of them declares: "The number of those who do not belong to my group and are in line ahead of me is even". In addition to this, the first three inhabitants in the line state, in order, the following: "There are 999 inhabitants in the village", "The Knights are exactly 666", "There are at least three Knaves in Asip". How many Knights are there in Asip?
Pick one
Solutions — 2
Solution 1
Solution:
The answer is (E). First of all we observe that the first person in line, ahead of whom there are 0 people, is necessarily a Knight, because he is necessarily telling the truth. Thus there are 999 inhabitants in Asip and at least one of them is a Knight. Let us focus on the statement concerning parity: the second person can be either a Knight (since ahead of him there are 0 Knaves), or a Knave (since ahead of him there is a Knight). In both cases, however, the third person in line belongs to the same group as the second. This also holds for the inhabitants further back in the line: whoever is in an even position has ahead of him an odd number of Knights and an even number of Knaves and can therefore be a member of either group; whoever, on the other hand, is in an odd position necessarily belongs to the same group as the person ahead of him. This tells us, in particular, that the Knaves are even in number. Let us then look at the other two statements of the inhabitants in second and third position: since they belong to the same group they either both tell the truth or both lie. In the first case we would have that the Knights are 666, while the Knaves are 333 (compatible with at least three), but this is not possible, because the Knaves must be even in number. Suppose then that they are both Knaves, then they are the only Knaves, otherwise the third person in line would be telling the truth. Hence all the other 997 inhabitants are Knights.
Solution 2
Solution:
As above, the inhabitants are 999. Suppose that the second person in line is a Knight: in that case the total Knights would be 666 and the Knaves 333. Let us then consider the last person in line: if he were a Knight, he would see 333 Knaves ahead of him, which is impossible (because he would be lying); but he cannot be a Knave either, because in that case he would see 666 Knights ahead of him. It follows that the second inhabitant in line is lying, hence he is a Knave, and therefore also the person behind him must be lying (he sees an odd number of Knaves and an odd number of Knights ahead of him). The Knaves are therefore at most two; indeed, the configuration in which everyone except the second and third in line are Knights (for a total of 997 Knights and two Knaves) is compatible with the statements of the inhabitants.
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.