A number of Knights and Liars went on a camping trip. Having pitched their tents for the night at the end of a long day's hike, Thomas (the best cook by far) settled down near the camp fire to make stew whilst everyone else sat in a circle around him, watching. Looking around, Thomas noticed that each person seemed to be sat between two people they knew, whereas Thomas himself knew no-one except his good friend Richard. So, getting everyone's attention, he asked a person at random in the circle the following question:
"You and the two people that are sitting next to you: Is there an odd number of Liars in that little group?"
The person replied. Thomas asked another person at random, and that person gave the same reply as the first. Again and again he asked and every time the reply was the same. Finally, having asked everyone else and always receiving the same reply, he turned to Richard and asked the question once more. Surprisingly, Richard answered differently to everyone else.
Thinking for a moment, Thomas asked Richard: "Are you sitting between two Knights?", to which Richard smiled and gave the same reply as he had previously.
Nodding, Thomas declared: "So, the Knights are outnumbered by the Liars here!", and turned back to making the stew once more.
If "n" people in total went on the camping trip, how many Knights and Liars are there, and what are Thomas and Richard?
Suppose somebody answers, "Yes" to the first question. Call this person A. If A is a knight, then there are an odd number of liars among A and the two people next to A. Since A is a knight, there cannot be 3 liars in A's group. Therefore, there is 1 liar, so A is between a knight and a liar. If A is a liar, then there are an even number of liars among A and the two people next to A. Since A is a liar, there cannot be 0 liars, so there are 2 liars among A and the two people next to A. Therefore, A is between a knight and a liar. That means that if A says, "Yes," then A is between two people of different types.
Suppose A says, "No" to the first question. If A is a knight, then there are an even number of liars among A and the two people next to A. If there are 0 liars in A's group, then A is between 2 knights. If there are 2 liars in A's group, then A is between 2 liars. If A is a liar, then there are an odd number of liars among A and the two people next to A. If there is 1 liar, then A is between 2 knights. If there are 3 liars, then A is between 2 liars. Therefore, if A says, "No," then A is between two people of the same type.
Suppose Richard was the only one who said, "Yes." Then, Richard is between a knight and a liar, but everybody else is between two people of the same type. Call the knight A and the liar B. Let A be the one on Richard's left. Since there are n people including Thomas, there are n-1 people in the circle. Since Richard is the only one sitting between two people of different types, B is the only one with somebody of the opposite type two to the left of them. Therefore, the person 2 to the left of A is a knight. Since B is a liar, all knights have a knight 2 to the left of them. Therefore, the person 4 to the left of A is a knight. Then, the person 6 to the left of A is a knight. We can continue this to show that the person 2n-4 to the left of A is a knight. However, 2n-4 to the left of A is the same as 2 to the right of A since there are n-1 people in the circle. The person 2 to the right of A is B, but B is a liar. Therefore, Richard was the only one who said, "No."
Since Richard said, "No," he is between two people of the same type, but everybody else is between two people of different types. He also said, "No" to the second question. If Richard is a knight, then he is not between two knights, so he is between two liars. If Richard is a liar, then he is between two knights. Therefore, Richard is between two people of a type different from him. Let Type R be Richard's type and Type R' be the other type. Then, Richard is between two people of Type R'. Call them A and B. Let A be the one on Richard's left. Since Richard is the only one sitting between two people of the same type, B is the only one with somebody of the same type two to the left of them. Therefore, the person 2 to the left of A is of Type R. Then, the person 4 to the left of A is of Type R'. For any integer x, the person 4x to the left of A is of Type R' and the person 4x+2 to the left of A is of Type R. We know that the person 2n-4 to the left of A is B, who is of Type R'. Therefore, 2n-4=4x for some integer x. Then, n-2=2x, so n=2x+2. That means that n is even. The person n-2 to the left of A is the same as 1 to the right of A. Therefore, the person n-2 to the left of A is Richard, who is of Type R. Since n-2 is even, it is either of the form 4y or 4y+2. Since Richard is of Type R, it is of the form 4y+2. Therefore, n-2=4y+2, so n=4y+4. That means that n is divisible by 4. Therefore, there are 4y+3 people in the circle. The people 1, 5, ..., 4y+1 to the left of Richard are the same as 4y+2, 4y-2, ..., 2 to the right of him, so they are all of Type R'. The people 2, 6, ..., 4y+2 to the left of Richard are all of Type R'. The people 3, 7, ..., 4y-1 to the left of Richard are the same as 4y, 4y-4, ..., 4 to the right of him, so they are all of Type R. The people 4, 8, ..., 4y to the left of Richard are all of Type R. Therefore, the people 1, 2, 5, 6, ..., 4y+1, 4y+2 to the left of Richard are all of Type R'. Also, the people 3, 4, 7, 8, ..., 4y-1, 4y to the left of Richard are all of Type R. That means that excluding Thomas, there are 2y+2 people of Type R' and 2y+1 people of Type R.
Suppose Thomas is a knight. Then, there are more liars than knights. If Richard is a knight, then there are 2y+2 knights and 2y+2 liars. If Richard is a liar, then there are 2y+3 knights and 2y+1 liars. There cannot be more liars than knights, so Thomas is a liar. Therefore, there are not more liars than knights. If Richard is a knight, then there are 2y+1 knights and 2y+3 liars. Now, there are more liars than knights, so Richard is a liar. Then, there are 2y+2 knights and 2y+2 liars. Since, n=4y+4, there are n/2 knights and n/2 liars. Therefore, Thomas and Richard are both liars, and there are n/2 of each type.
Edited on September 10, 2012, 3:38 pm
|
Posted by Math Man
on 2012-09-10 14:25:58 |