Maths Olympiad Prep

Library / /37 of 39

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Italy

Problem:

On the Island of Knights and Knaves, Knights tell the truth except when they make a mistake, and Knaves always lie. During a meeting, 40 islanders sit around a large round table and each one says: "I am next to a Knight and a Knave". Knowing that 3 Knights present are mistaken, how many Knights are at the meeting?

Solution

Solution:

The answer is 2727.

Let us begin with some basic observations. There cannot be only Knights at the table, because they would all have to be mistaken and not just 3 of them. If we look at a Knave or, equivalently, a Knight who is mistaken, next to him sit either two Knaves or two Knights.

Since there is at least one Knave and at least one Knight (actually at least three), there is at least one Knave sitting next to a Knight. In particular the Knaves (assuming there is more than one) cannot sit next to each other, since those "inside" the group could lie, but those on the edge would have a Knave neighbor and a Knight neighbor, which is absurd. Thus the Knaves sit isolated, surrounded by Knights.

Basically, without the Knights who are mistaken, we would then have a sequence of triples of the form CFCC F C.

Let us now bring into play the Knights who are mistaken. They can insert themselves between two Knights (for example between two consecutive triples, but not only there, if there are several in a row) or between two Knaves, that is "eliminating" a Knight, when we look at two consecutive triples: CFCCFCC F C C F C can be replaced by CFCˉFCC F \bar{C} F C, where Cˉ\bar{C} is the Knight who is mistaken. In the first case the number of people at the table increases by 1, in the second it decreases by 1 (two Knights are "transformed" into a single Knight).

Let us say there are aa mistaken Knights of the first type, that is, sitting between Knights, and 3a3-a of the second, that is, between two Knaves. Then at the table there are 40=k3+a(3a)=3(k1)+2a40 = k \cdot 3 + a - (3-a) = 3 \cdot (k-1) + 2a, with 0a30 \leq a \leq 3. Since 40 has residue class 1 modulo 33, 2a2a has residue class 1 modulo 3, hence a=2a=2. This means that we have two mistaken Knights surrounded by Knights and one surrounded by Knaves.

Before considering the mistaken Knights, we had 39 people sitting around the table, of whom 26 were Knights and 13 were Knaves. We added two Knights (who are mistaken) sitting between other Knights, bringing the total number of Knights to 28, after which the third mistaken Knight took the place of two Knights sitting next to each other and surrounded by Knaves, which reduced the total number of Knights to 27.

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.