Question

In: Advanced Math

A terrible despot governing one small country decided to check how smart are people living in...

A terrible despot governing one small country decided to check
how smart are people living in his country. He gathered 20 smartest people
and put hats on their heads. Everybody could see all hats except their own.
Then the despot said: "Some of the hats have a red stripe on them. I will
give you one minute to think and then ask who has a red stripe on their
hat? If nobody answers, then I will give one more minute and ask the same
question again. I will repeat it 100 times. If you guess somehow that you got
stripe on the hat you have to wait till I ask my question and say immediately
about that, because after somebody will gure out correctly that he or she
has a stripe on the hat, I will kill everybody else who has the stripe and did
not gure it out. If you say that you have a stripe and you don't , I will kill
you. " They know that each of them is really good at deduction (got A for
Math 311W when they were in college) and nobody wants to die.
a) Prove that if 2 people have red stripes on their hats, then after the terrible
despot will ask them second time all of them will say that they have them,
and despot won't be able to kill anybody.
b) What happens if three people have stripes?

Solutions

Expert Solution

Both parts are done in a similar way, so I will describe them together. Let us assume for starters, that only one person had a stripe on his/her hat. In that case that person can't see stripe on anyone else's hat. But when the despot says that there is at least one person with a stripe on his hat, the person with a stripe can easily conclude that it his/her own hat that has the stripe and will announce immediately after the first time.

Now we go to the case when two people have stripes on their hat. Let those person be called A and B. A  can see only one other person with striped hat(that is B). From A's point of view there are two cases, his hat is striped or it not striped. If his hat is not striped then there is only person with a hat on his head. Therefore from the previous discussion that person will announce that he/she has a striped hat immediately after the first question. But since B has the same observations he will not announce that he has striped hat after the question. Therefore A can conclude that B is seeing one more striped hat and hence was not able to conclude that he himself has a striped hat. Since no other person has a striped hat it means that A can conclude that he has striped hat and will announce the fact after the second question. B making the same observations will conclude the same thing and will announce he has a striped hat.

In the case three striped hats, following the same line of argument, all three will see people with two striped hats. From the previous para, those people will assume that if they don't have the striped hat, other two will announce that they have striped hat after 2 times. Since they will not, all three can conclude that they also have striped hats and will announce it after 3 times the question is asked. (The other people who could see three striped hats, will wait for the 4th time, but this will not happen, as the 3 people will announce the fact after the 3 time itself).

The logic is taken from the famous Blue Eyed Problem.


Related Solutions

The following is the data on the income of people living in country A and B....
The following is the data on the income of people living in country A and B. Income # of population in Country A # of population in Country B 10000 1000 4000 20000 5000 5000 30000 4000 6000 40000 12000 6500 50000 10000 5200 60000 6000 4600 70000 4500 5200 80000 3500 6500 90000 2500 3400 100000 1500 3600 Depict the income data on a Lorenz curve for country A Depict the income data on a Lorenz curve for country...
How can a small business check their credit?
How can a small business check their credit?
Introduction: Social contract theorists say that morality consists of a set of rules governing how people...
Introduction: Social contract theorists say that morality consists of a set of rules governing how people should treat one another that rational beings will agree to accept for their mutual benefit, on the condition that others agree to follow these rules as well. Hobbes runs the logic like this in the form of a logical syllogism: We are all self-interested. Each of us needs to have a peaceful and cooperative social order to pursue our interests. We need moral rules...
Introduction: Social contract theorists say that morality consists of a set of rules governing how people...
Introduction: Social contract theorists say that morality consists of a set of rules governing how people should treat one another that rational beings will agree to accept for their mutual benefit, on the condition that others agree to follow these rules as well. Hobbes runs the logic like this in the form of a logical syllogism: We are all self-interested. Each of us needs to have a peaceful and cooperative social order to pursue our interests. We need moral rules...
Public Goods Two people living in the same small neighborhood make up the total demand for...
Public Goods Two people living in the same small neighborhood make up the total demand for streetlights: P1= 200-2Q P2= 100-Q assume streetlights in the area a pure public good. A. Define Pure Public good. Briefly explain why the private sector might fail to produce enough pure public goods. B. Assume the streetlights can be provided at $240 per unit. Why would it be inefficient to just charge each person $120 per lighthouse (split the cost between them)? C. What...
QUESTION 1. On average, one in every 1000 people living in a city is known to...
QUESTION 1. On average, one in every 1000 people living in a city is known to have cancer. In a study carried out in this province, 5000 people were checked for health. According to this; a) Calculate the probability that 7 out of 5000 people will get cancer. b) Calculate the probability that no more than 1 person out of 5000 can get cancer.
Which of these people will buy one of the three beachfront parcels? Check all that apply....
16. How prices allocate resources Suppose that there are three beachfront parcels of land available for sale in Astoria and six people who would each like to purchase one parcel. Assume that the parcels are essentially identical and that the minimum selling price of each is $575,000. The following table states each person's willingness and ability to purchase a parcel. Which of these people will buy one of the three beachfront parcels? Check all that apply. Antonio Caroline Dmitri Frances Shen Valerie Assume that the three beachfront parcels are...
Unemployment Question The small country of Macroland has a population of 100,000 people over the age...
Unemployment Question The small country of Macroland has a population of 100,000 people over the age of 18 and under 65. There are 50,000 people under the age of 18, and 20,000 people over the age of 65. The number of people between ages of 18 and 65 that are looking for jobs is 20,000, and the number that have jobs is 50,000. Using this information, answer the following questions. Show your work. These are numbers for the month of...
1. In country A, the population is 330 million and 100 million people are living below the poverty line. What is the poverty rate?
1.  In country A, the population is 330 million and 100 million people are living below the poverty line. What is the poverty rate? 2. In country B, the population is 127 million and 19 million people are living below the poverty line. What is the poverty rate? 3. Imagine federal legislation is passed granting every U.S. resident a $20,000 per year universal basic income. No matter the income an individual earns from working, this $20,000 per year level of...
Twenty people check their hats at a theater. In how many ways can their hats be...
Twenty people check their hats at a theater. In how many ways can their hats be returned so that (a) no one receives his or her own hat? (b) at least one person receives his or her own hat? (c) exactly one person receives his or her own hat?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT