; 2
!"#$%&'()*+,-./013Root Entry
!"#$%'()*+
FMicrosoft Word-Dokument
MSWordDocWord.Document.89q
[ttDefault$$a$A$d1$
*$/B*OJQJCJmH sH PJ^JaJ_HtHnHBA@BAbsatz-StandardschriftartBBWW-Default Paragraph Font.B. Text body
x / List^J@"@Caption
xx$CJ6^JaJ]&2&Index$^JNBNWW-List Paragraph^]`P>'7tj><&+61357 !"#$%&'.WW8Num4@PGTimes New Roman5Symbol3&Arial7&Calibri5TahomaBhiEiE'0Oh+'0$
p x
5@@CM@pXM@s
MAdministratorAdministratorNormalM 07Caolan70,P
l888L4TY$6} D:,8Welcome to TrueFalse Island!
You decide to take a vacation to the strange and lovely TrueFalse Island, fascinated that the native peoples are divided into two curious types: those that always tell the truth, and those that always lie. Despite this difference, they all live together in one village and get along very well with each other, and you find that they are very polite to you, perhaps because you are the only tourist on the island for the moment.
At first you find it a little disorienting that it is impossible to tell who is a truth-teller and who is a liar just by their appearance, but eventually you realize that there are specific questions (with yes or no answers) that you might ask any islander to determine what type he or she is. What s an example of such a question? Why does it work?
Later a friend of yours, a native who always tells the truth, tells you that on the island it is customary to learn the inhabitants types simply by paying careful attention to what they say to one another, instead of asking questions all the time. You do your best to follow his advice whenever possible.
You overhear three natives, A, B, and C talking quietly. A whispers something to B which makes him laugh. C asks what B what A told him, and B says He told me that he is a liar.
Can you determine the type of A or B from this exchange alone?
A pair of natives A and B are chatting, and A says, We are definitely the same type.
Can you be sure about the type of A or B?
A, B, and C are having a discussion.
A says: All three of us are liars. I m so happy! B says. Actually, exactly one of us is a truth-teller. Sorry to disappoint you.
What are the types of A, B, and C?
Pleased with your command of logic, you tell your truth-teller friend about this most recent success in island etiquette. He says, Oh, your reasoning is sound, but I thought B actually said, exactly one of us is a liar, not exactly one of is a truth-teller.
If your friend is correct about what B really said, can you still find of the types of A,B, and C?
A says to you, B and C over there the same type as me. You walk over to B and C, and ask C, Are A and B the same type? He is about to respond when you suddenly realize that you won t be able to make any conclusion from listening to him.
Why can t you draw information from C s response (and what will C say)?
You come across A and B, and ask A, Is either of you a truth-teller? Based on the answer he gives you, you are able to find the correct answer, but later it occurs to you that had he answered differently you would have been unable to conclude anything.
What was his answer, and what are the types of A and B?
There is an annual island-wide party in which all the natives form a large circle and eat and sing and dance. You are invited to the party, but according to tradition you are not allowed to be part of the circle. You amuse yourself by going around the circle asking each person Is the person on your left a truth-teller? Amazingly, everyone answers No. After the party you ask a random person how many people live on the island, and he says, 99, but another native overhears this are tells you, Sorry, this man is a liar. There are 100 inhabitants here.
How many people live on the island?
You soon learn that off-shore a few miles from TrueFalse Island is another island called Random Island, inhabited by people who randomly tell truths and lies. Your trust-worthy native friend tells you some of these people may be visiting TrueFalse Island soon but he s not sure when.
You meet two people A and B. A say to you, My friend B here always lies. Yep, says B, A always tells the truth. A native gentleman C who you know (but whose type you never bothered to discover) says Ah, you two guys are natives of this island.
What type is C?
You are talking to A, B, and C. You re sure that one is a truth-teller, one a liar, and the other a non-native from Random Island, but you re not sure which is which. A says, B is from Random Island, and B says C is from Random Island. C points to one of the other two and says, That guy is definitely from Random Island. You are certain that you know who the Random Islander is.
Who did C point to (in order for your conclusion to be certain)?
Hint: To get started, suppose C points to A. Can you be certain who is the Random Islander? Now suppose C points to B instead. Can you be certain who is the Random Islander?
Eventually, all the visitors from Random Island decide they want to stay permanently, and coincidently, they all join the army. To keep everyone straight, the TrueFalse army ranks soldiers according to type: truth-tellers are the highest rank, followed by the middle ranking Random immigrants, and liars are ranked lowest.
You hear two soldiers A and B arguing: A says, I am of lower rank than you, but B responds, That s not true!
What are the ranks of A and B? Can you tell if their statements are true or false?
You get lost on the island one day and become worried about finding the way back to the village. Eventually you find a road, which is helpful since you happen to know that the island has only one road, connecting the village on one side of the island to the airport on the opposite side, but you are so turned around you don t know which direction to walk. Suddenly you see someone else coming toward you, and judging by his clothing you decide he can t be a soldier, and thus he is definitely a native.
Assuming that this native knows which direction to take to reach the village, can you find one question (with a yes or no answer) that will allow you to determine the right direction?
You meet three natives and you know that two of them are one type and the other is a different type, but nothing more.
Can you find two (yes/no) questions you might ask to determine how many of each type are in the group?
Can you find just one such question that can accomplish these tasks? Why or why not?
You meet three natives and you know that at least one is a truth-teller.
What's the minimum number of questions needed to determine how many truth-tellers are in the group?
What's the minimum number of questions needed to determine the types of everyone in the group?
You meet three people and you re certain that one is a truth-teller, one a liar, and one from Random island, but that s all you know.
Can you think of three (y/n) questions you might ask to determine their types?
6>`
b
d
f
h
j
@&6~fhjlnprtZhjlnprtvxz|~8:<>@BDF """""""""%<&'>'OJQJCJaJaJCJOJQJaJCJOJQJ>*Y>'''''''.*++++++++++/0121416181:1<1>1.223333333333N45555555567OJQJCJaJaJCJOJQJ1>`
b
d
f
h
j
@
&F^]`&6~fhjlnprt
&F^]`
h^h]`tZhj~pn
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
&F^]`jlnprtvxz|~8:<>
h^h]`
h^h]`
h^h]`
h^h]`
&F^]`>@BDF """""""""%<&
h^h]`
&F^]`
h^h]`
h^h]`
h^h]`
h^h]`<&''''''.*++++~pb
h^h]`
h^h]`
h^h]`
&F^]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`+++++++/01214161~pb
h^h]`
h^h]`
h^h]`
h^h]`
&F^]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`6181:1<1>1.2233333~pb
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
&F^]`
h^h]`
h^h]`
h^h]`
h^h]`333333N455555~pb
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`
&F^]`
h^h]`
h^h]`
h^h]`
h^h]`
h^h]`555567
&F^]`
h^h]`
h^h]`
h^h]`*/ =!"#$2P1h3P(20Root Entry FCompObjjOle
1TableSummaryInformation(&TWordDocument ,P