Fresh Cute Logic Puzzles
Recently, I stumbled upon three lovely logic puzzles, while scrolling Facebook for news from the Russia-Ukraine war. I will start with an easy puzzle.
Puzzle. A traveler got to an island, where each resident either always tells the truth or always lies. A hundred islanders stood in a circle facing the center, and each told the traveler whether their neighbor to the right was a truth-teller. Based on these statements, the traveler was able to clearly determine how many times he had been lied to. Can you do the same?
In the next puzzle, there is another island where people are either truth-tellers or normal. There are three questions that increase in difficulty.
Puzzle. You are on an island with 65 inhabitants. You know that 63 inhabitants are truth-tellers who always tell the truth, and the other 2 are normal, who can either lie or tell the truth. You are allowed one type of question, “Are all the people on this list truth-tellers?” This question requires a list, which you can create yourself. Moreover, you can have as many different lists as you want. You can pose this question to any islander any number of times. Your goal is to find the two normal people. The easy task is to do it in 30 questions. The medium task is to do it in 14 questions. The hard task is to figure out whether it is possible to do it in fewer than 14 questions.
Here is the last puzzle.
Puzzle. You got to an island with 999 inhabitants. The island’s governor tells you, “Each of us is either a truth-teller who always tells the truth, or a liar who always lies. ” You go around the island asking each person the same question, “How many liars are on the island?” You get the following replies.
First person, the governor: “There is at least one liar on the island.”
The second person: “There are at least two liars on the island.”
This continues progressively until the 999th person says: “There are at least 999 liars on the island.”
What can you tell about the number of liars and truth-tellers on this island?
Share:
rosie:
In the first one, whatever sequence of statements the islanders had made, they would’ve made the same sequence in a second scenario where each islander had switched tribe. But each truth in the first scenario is a lie in the second. So how could the traveller know how many times he’d been lied to? The only way is if the statements were 50 truths and 50 lies. So the answer is 50.
14 August 2022, 12:14 pmrosie:
Third problem. If there are x liars, then the first x statements are true. The rest are lies, and so the people that made them are liars, so there are 999-x liars. But these numbers have opposite parities and therefore cannot be equal. This contradicts the statements that “Each of us is either a truth-teller who always tells the truth, or a liar who always lies.” But the governor said that. So they lied. Their statement that there is at least one liar turns out to be true, if we take “liar” to mean someone who doesn’t always tell the truth. But we have no reliable basis for inferring that any islander either always tells the truth or always lies. The only thing we can deduce is that the governor sometimes lies.
14 August 2022, 12:29 pmchristian:
For the last question, the number of truth-tellers is immediately no greater than 499, since if the 500th person is telling the truth, then every previous person is also telling the truth, leaving no more than 499 possible liars remaining, so the 500-999th people must be lying.
And if the 500-999th people must be lying, this must mean that there are at least 500 liars (since we include the 500th person in our tally), meaning that the 1-499th people are telling the truth about the number of liars. Therefore, there are 499 truth tellers and 500 liars.
14 August 2022, 7:39 pmOscar Cunningham:
I think I can do the middle puzzle in 13 questions. I’ll name some of the people to make it easier to keep track.
Pick 17 people and ask another person, Alice, if they are all trustworthy. If she says yes then also ask Bob if all 17 are trustworthy. If he also says yes then they must in fact all be trustworthy, because either at least one of Alice and Bob are trustworthy, in which case we believe them that the 17 are trustworthy, or neither of them are in which case there are no remaining untrustworthy people to be among the 17. We can then ask our 11 remaining questions to one of the 17 to find the 2 untrustworthy people among the 48 others (proof below).
If Alice says yes and Bob says no, then we know at least one of Alice and Bob is untrustworthy. Now ask Charlie whether Dan is trustworthy. If he says yes then Dan must be trustworthy, by similar logic to the above. Then ask Dan if Alice is trustworthy, either answer will determine at least one untrustworthy person among Alice and Bob. Use 6 questions to binary search all the other people to find the other untrustworthy person. If Charlie says no, then one of he or Dan must be untrustworthy, and we can use 2 questions to any of the remaining people to find who is untrustworthy out of Alice and Bob, and Charlie and Dan.
If Alice says no then either her or one of the 17 is untrustworthy. Now pick 17 new people and ask Charlie if they are trustworthy. If he says yes then they must be trustworthy, and we can use our 11 remaining questions to find the two remaining untrustworthy people among the 48 others. If Charlie says no then one of he or the 17 is untrustworthy. Then any of the remaining people is trustworthy, and we can ask the 5 question to binary search each of the sets of 18.
It remains to show that we can find 2 untrustworthy people among 48 by asking 11 questions to someone who is known trustworthy. Do this by splitting them into 3 sets of 16 and asking the person about each of these sets. If the untrustworthy people are in different sets then we can use 4 questions on each set to binary search them. If they’re in the same set then we can use binary search to find one of them, and then binary search the remaining 15 people to find the other.
15 August 2022, 5:53 amOscar Cunningham:
Assuming my above comment is correct, there is still the issue of whether it can be done in fewer than 13 questions. There is some slack in my above argument so it might be possible to reduce the number of questions. Certainly we cannot do less than 12 since 2^11 < 65C2 < 2^12, so we would not have enough possible answers to distinguish all situations. It would be useful if we knew an optimal strategy once we have found a trustworthy person.
15 August 2022, 6:00 amOscar Cunningham:
For the last question, rosie is right that the governor must have lied when he said there were only truth tellers and liars. But we can still deduce some things about the number of truth tellers and liars. Let us call the people who are neither truth tellers or liars ‘normal’. The governor cannot be a liar, or else he would have told the truth when he said there is at least one liar. So he must be normal. Let us suppose there are T truth tellers and L liars. We want to know for which values of T and L there is an assignment for each of the islanders to truth teller, liar, or normal such that all the truth tellers are telling the truth and all the liars are lying. Note that the islanders statements are increasing in strength, so we never make a consistent assignment inconsistent by swapping a truth teller with someone above them in the ordering, or a liar with someone (other than the governor) below them in the ordering. So we may assume that the ordering is the governor (normal) followed by T truth tellers, 998-T-L normal people, and L liars. Then the first L people are telling the truth, and the last 999-L people are lying. Hence T+1 <= L and L <= 999-L. In other words there are 499 or fewer liars, and at least one fewer truth teller than liars. All numbers of truth tellers and liars obeying this constraint are consistent.
All this assumes that the inhabitants of the island are not including the questioner when they make their statements. Otherwise a similar analysis applies, except that it is also possible that the governor is one of 500 truth tellers, and there are also 500 liars including yourself.
15 August 2022, 6:51 amZarunias:
For the first problem you can alter it to a out-of-the-box-thinking one, if you change the number from 100 to 99 (or any other odd number).
The question “Can you do the same?” would then be answered with “Yes, you lied to me once when you told me that the traveler could find out how many liers there are.”
24 August 2022, 12:57 pmTanya Khovanova's Math Blog » Blog Archive » Fresh Cute Logic Puzzles - New Marathi Live:
[…] Source link […]
16 September 2022, 8:14 am