In the island of knights and knaves, knights always tell the truth and knaves always lie. During a reunion, the participants sit around a large round table, and everybody says, "The person on my left is a knave." Knowing that there are fewer than 100 knights, which of the following is a possible number of participants?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
We claim that if A says "B is a knave", then A and B are different (one is a knight and the other is a knave). We can easily check this case-by-case: if A is a knight, then B is a knave, and if A is a knave, then B shouldn't be a knave, and thus B is a knight.
Thus the statement in the problem is equivalent to the statement that every pair of neighboring people are different. If we number the people 1 , 2 , 3 , … , n in order, then we can prove by induction that the odd numbers have the same alignment as 1, and the even numbers have the same alignment as 2; that is, the odd numbers are all knights or all knaves, and so as for the even numbers. (The proof is simple: the base case is proven for 1 and 2, because one has the same alignment as oneself. If we have shown the statement stands for people numbered k , k + 1 , then k and k + 2 each has different alignments from k + 1 , so k and k + 2 must have the same alignment. If k is odd, then k + 2 has the same alignment as k , which has the same alignment as 1, so k + 2 has the same alignment as 1. The proof if k is even is similar.)
Now that we have shown this, we can prove that n is even. Since, if n is odd, then 1 and n neighbor each other and thus should be different, but we proved n and 1 have the same alignment, contradiction. Thus n is even. Moreover, there must be 2 n knights and 2 n knaves; the odd numbers make 2 n of the people, and so as the even numbers, so whichever of them is the knights, we have 2 n of them. (Clearly we must have exactly one of the two sets to be knights; if there are zero, then everyone are knaves; if there are two, then everyone are knights, both wrong.)
Thus the conditions are n is even, and 2 n < 1 0 0 . Among the choices, only 192 works.