Let’s say that there are knights on the city council. If we can figure out what the value of is, we’ll be practically done. We can start our exploration with a couple of extreme cases:
- If , then all of the councilmembers are liars. But then the first councilmember’s statement is true, and since liars never tell the truth, that means the first person is a knight. But we assumed that , meaning knights! So this case is impossible.
- If , then all of the councilmembers are knights. But then the first councilmember’s statement is false, and since knights never say things that are false, that means the first person is a liar. But means there aren’t any liars! So this case is impossible also.
Okay, so we know that . (This tells us immediately that the first councilmember is a liar and the twelfth one is a knight – make sure you can see why.) We could keep working through each case individually, crossing out options each time something doesn’t work, but that seems like a pretty long process… is there a faster way?
Let’s take another look at which of the councilmembers’ statements are true when there are knights.
When the second councilmember says “Not more than person in this room tells the truth,” the statement is equivalent to “There are or fewer knights in this room.” If , then the statement is true and the councilmember is a knight, but if , the statement is false and the councilmember is a liar. We can do the same thing for all the others: e.g. the eighth councilmember’s statement is equivalent to “There are or fewer knights in this room,” which is true (and therefore the councilmember a knight) for and false (and thus the councilmember a liar) for .
Whoever says “Not more than people in this room tell the truth” (for whatever the value of is) is saying a true statement (since ) and so must be a knight. And all the people who speak after that person set increasingly large upper bounds on the number of knights, so they’re all telling the truth also and thus must also be knights. But whoever says “Not more than people in this room tell the truth” is saying something false (since ) and so must be a liar. And all the people who speak before that person also set upper bounds that are too low for the number of knights, so they’re also lying.
Since everybody after “Not more than people in this room tell the truth” (i.e. councilmember ) is a knight and everyone before that is a liar, and we defined to be the number of knights, we can take the last councilmembers and say with confidence that they are knights: this means council members through . And we know that since council member is the first knight to speak after that turnaround point from liars to knights, and that person says “Not more than people in this room tell the truth,” we can conclude that there are exactly knights in the room (since any smaller cap on the number of knights will result in a false statement by one of the liars).
Hold it. We just concluded that there are exactly knights in the room. But we defined as the number of knights in the room. If we want a solution to this puzzle that follows all the constraints, these two numbers must be equal:
This is an equation we can solve! We add to both sides:
And then we divide by :
And there we have it! There must be knights in the room, and therefore liars. Try checking our solution against the councilmembers’ statements to confirm it works!