How many people?
You are in a country where exist only two types of people: knights, that always tell the truth, and knaves, that always lie. You saw a circle of people. All people in there made the statement below:
| Both people next to me are knaves. |
What is the smallest value of in order to guarantee (not depend on luck) that the circle have 6 knights ?
The answer is 16.
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.
1 solution
One approach to answering this question is to determine the maximum number of people who could be in a circle with exactly 5 knights, and then add one to that number.
Since everyone made the statement "both people next to me are knaves," we know each knight has to be next to two knaves, and no knave can be next to two knaves. Otherwise, we would have a knight lying or a knave telling the truth, both of which are impossible. Since no knave can be next to two other knaves, we know there can't be three knaves in consecutive positions in the circle.
Suppose we have a circle with 5 knights. Going clockwise around the circle, we'll call our knights A, B, C, D and E. Since knights can't be beside each other, there must be a group of one or more knaves in each of these 5 positions: between A and B, between B and C, between C and D, between D and E, or between E and A. Since we already know we can't have 3 consecutive knaves, the maximum number of knaves in any of those 5 positions is 2, for a maximum total of 10 knaves. This means the maximum circle size with 5 knights is 15. Using K to represent a knave, our 15-person circle could be as follows: KAKKBKKCKKDKKEK. Since it's a circle, rather than a line, the knaves on either end would wrap around. Notice that attempting to add any additional knaves to that circle would force a group of 3 consecutive knaves.
Since the maximum number of people in a circle with 5 knights in 15, the minimum size of the circle that's guaranteed to have at least 6 knights is 16.