Maths Olympiad Prep

Library / /68 of 75

Combinatorics Difficulty 6.3 National Olympiad Prove it Italy

Problem:

On an island there are 2023 people standing in a line, each of whom is either a knave or a knight: knights always tell the truth, while knaves always lie. If ii is odd, the person in position ii-th exclaims: "There are at least ii knaves"; if ii is even, the person in position ii-th exclaims: "There are exactly ii knaves". How many are the knaves?

Solution

Solution:

The answer is 1348. If the knaves are odd in number, say 2m+12m+1, then the people who tell the truth are all and only those in odd positions less than or equal to 2m+12m+1, which are m+1m+1. There would then be 2m+12m+1 knaves and m+1m+1 knights, for a total of 3m+23m+2 people, but this is impossible since the equation 2023=3m+22023=3m+2 leads to m=20213m=\frac{2021}{3}, which is not an integer. The knaves are therefore even in number, say 2m2m: the knights will be all and only the people in odd positions less than or equal to 2m2m, plus the person in position 2m2m, hence in total m+1m+1. Thus 3m+1=20233m+1=2023 and therefore the knaves are 2m=13482m=1348. One verifies that the configuration works.

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.