And yet another math problem - optimum survival strategy

[T. R. Oglodyte Moderator Find all posts View Profile Close T. R. Oglodyte]

Earth has been invaded by the Marvin the Martian:



After getting completely frustrated dealing with Elmer Fudd,
,
Marvin decides to eliminate all human beings who can’t demonstrate basic skills in thinking and cooperation. Think of this as the ultimate enforcement an ultimate enforcement hammer for “No Human Gets Left Behind”.

Marvin sets up the following test:

• People are placed in groups of 100, and lined up on a stairway with 100 steps, each person facing up the stairs so they can see all people above them and no one below them.
• After they are lined up the Marvin places a beanie on each person’s head. The beanie is either red or black. Each person can see the color of the beanies of all of the people ahead of him or her on the stairs, but cannot see the beanies of any person behind. No person can see the color of his or her own beanie.
• Starting at the bottom stair and proceeding in sequence up the stairway from the bottom stair to the top stair, Marvin asks the person the color of their hat. If the person answers correctly, the person lives. If the person answers incorrectly, Marvin immediately vaporizes the person using his Acme Model XZ-200 Quasi-Sentient Being Vaporizing Laser.
• Each person can hear the answer provided by each person behind them on the steps, and knows whether or not Marvin vaporized the person.
• When questioned, a person may say only “red” or ‘black”. No other words may be said. The person may not use any tone of voice, inflection, pitch, volume, etc. to convey any other information. Any attempt to convey information in any manner other than a simple answer of “red” or “black” will be detected by Marvin's Acme Model 32QZ Brain Wave Information Analyzer and will result in Marvin immediately vaporizing all 100 people.
• When lined up, no person may say anything to any other person, may not turn around, nor do anything that conveys any information to other participants other than saying “Red” or “Black” when Marvin asks the color of their beanie. Any attempt to gather or convey information in any other manner will be detected by Marvin’s Acme Model 32QZ Brain Wave Information Analyzer and will result in Marvin immediately vaporizing all 100 people.
• Before the people are lined up on the stairs, they are locked in a room together for one hour to plan strategy. At the end of the hour Marvin lines them up on the stairs. Once Marvin unlocks the door to the room, no further communication is allowed. Any attempts at further communication will be detected by Marvin’s Acme Model 32QZ Brain Wave Information Analyzer and will result in Marvin immediately vaporizing all 100 people.
• The breakdown between the number of black beanies and red beanies is totally random. The number of beanies of any color is equally likely to be any number between zero and 100. The only constraint, of course, is that the total number of beanies will equal 100.

What strategy should the people follow to maximize the number of people who survive? How many people can be guaranteed to survive following this strategy?

P.S.: This is not a trick problem, and any trick or confusing words or phrases are unintentional.

[kkan Junior Member Find all posts View Profile Close kkan]

Interesting riddle.

First number the hundred people from bottom to top 1-100. Every odd numbered person should say the color of the person in front of him rather than guessing. Every even numbered person should just repeat the color that was said by the person immediately before him.

I think you will achieve a 75% survival rate this way.

[kkan Junior Member Find all posts View Profile Close kkan]

Better idea.

Again number the people from bottom to top 1-100. Groups of three will work together. Person #1 should say "red" if #2 and #3 are the same color and "black" if they are different colors. #2 by looking at #3 now knows his color (because #1 told him whether his color is the same or not as #3) and should say it. #3 now knows his color also because he heard the answer by #2 and knows if he has the same color or not. #3 should now say his answer.

Working in groups of three, #4 should do the same as #1, #5 should do the same as #2, and #6 should do the same as #3. The cycle can be continued through all 100 people.

The survival rate now improves to 83%.

[T. R. Oglodyte Moderator Find all posts View Profile Close T. R. Oglodyte]

Here's a better way. The first seven people count the number of black beanies in positions 8 through 100 and convey that number in binary code, using black as "0" and red as "1".

For example, let's say there are 76 black beanies in positions 8 through 100. 76 in binary is 1001100. then the first 7 people call out, in order, red - black - black - red - red - black - black. Every person from position 8 through position 100 then knows how many black beanies there are after position #7.

The person in position #8 counts the black beanies ahead of him or her. His or her count will either be the same as the number called by the preceding people, or it will be one less. If it's one less, then person #8 knows his or her beanie is black; if the count is the same then his or her beanie must be red.

Beyond position #8 each person simply counts the black beanies they can see, and keeps a tally of how many black beanies remain. When a person's turn comes, the person compares the remaining tally with his or her count of black beanies beyond his or her position. If the tally and the count match, then that person's beanie must be red. If the count is one less than the tally, then that person's beanie must be black.

That method assures the survival of 93 of the people, and the remaining 7 each have a 50% chance of survival.

****

There is a method, though, that guarantees survival of 99, with the last person having a 50% chance.

[Jya-Ning Silver Contributor Find all posts View Profile Close Jya-Ning]

There is a method, though, that guarantees survival of 99, with the last person having a 50% chance.

With a hint like that. I will guess the last person use red or black to indicates if the total number of black (or red) bean is even or odd number. So, the person before last person look at total black bean before him(her), and since (s)he know it should be a odd (or even) number, the bean's color can be known.

Of course, in reality one guy dozzy off, and mis count, (s)he get vaporized, but the person before him (he) know it is wrong count, so it can still continue.

Now if the last person count wrong ... better hope I am not the last one.

Jya-Ning

[T. R. Oglodyte Moderator Find all posts View Profile Close T. R. Oglodyte]

With a hint like that. I will guess the last person use red or black to indicates if the total number of black (or red) bean is even or odd number. So, the person before last person look at total black bean before him(her), and since (s)he know it should be a odd (or even) number, the bean's color can be known.

Of course, in reality one guy dozzy off, and mis count, (s)he get vaporized, but the person before him (he) know it is wrong count, so it can still continue.

Now if the last person count wrong ... better hope I am not the last one.

Jya-Ning

That's right. The person on the bottom step can see 99 beanies. When he counts red and blackbeanies, one of those numbers will be even and the other will be odd.

Let's say the group decides that the person on the bottom step will call black if that person counts an odd number of black beanies and red if the person's count is read.

Let's say he calls red. Then the person in the next position counts the red beanies ahead of him. If he or she counts an odd number of red beanies, then that person knows his or her beanie is black. But if he or she counts an even number of beanies then that person knows his or her beanie must be red.

By tracking red beanies as they occur, each successive person will know whether the red beanie count at his or her position should be odd or even. By comparing that information with that person's red beanie count, that person will know if his or her beanie is red or black.

[Jya-Ning Silver Contributor Find all posts View Profile Close Jya-Ning]

Now if the last person count wrong ... better hope I am not the last one.

I know, if the last person count wrong, the one before him(her) will got zapped. At that moment, either that person miscount, or the person before him miscount, so the odd/even number should be correct as stated as last person.

So, if it is a perfect world, 99 people get saved, 1 people have 50% chance survive, if it is not, all except the one before last one will be able to survive depends on if (s)he can count. And to be able to tell the color of a bean from black and red 100 steps before me, that is a scare thought.

I am not going to be 99th person.

Jya-Ning

[BILL_B Member Find all posts View Profile Close BILL_B]

"Marvin decides to eliminate all human beings who can’t demonstrate basic skills in thinking and cooperation."


I suggest that if Marvin wants to get off to a good start and achieve a 100% kill factor that his first stop should be at RCI

Bill

[T. R. Oglodyte Moderator Find all posts View Profile Close T. R. Oglodyte]

"Marvin decides to eliminate all human beings who can’t demonstrate basic skills in thinking and cooperation."


I suggest that if Marvin wants to get off to a good start and achieve a 100% kill factor that his first stop should be at RCI

Bill

I could have also set it up so that Marvin starts an upfront fee listing company, then vaporizes everyone who signs up and pays the money.