What Strategy Saves the Most Prisoners?

[qspeechc]

Riddle 1
30 Prisoners are on death-row for marijuana related offences. The prison warder doesn't view their crimes with much seriousness,and decides to give them a chance to escape.He makes the prisoners the following offer:
Tomorrow all the prisoners will be blindfolded, and either a black or a white hat wil be placed on their heads. All the prisoners will then be placed in a row, all facing the same direction in line with the row (so all but one is facing someone elses back). Then their blindfolds will be removed. They cannot see their own hat, or those on the people behind them. But they can see all the hats of the people in front of them.
The deal is that the prisoners themselves get to guess what colour hat they are wearing. If they guess correctly, they will be freed. Otherwise not. Thus the prisoners are faced with finding some strategy to maximise the number of prisoners that will be freed. What is this strategy, and how many prisoners will be garuanteed their freedom? And how many prisoners will be freed using it?

Riddle 2

Suppose there are 17 scientists. Each scientists corresponds (writes letters etc.) with each other scientist, and they correspond about only 3topics, and any two scientists correspond about exactly one topic with each other. Show that there exists at least three scientists who correspond with each other about the same topic.

 

[qspeechc]

Nobody ? :(

 

[RandallB]

Put a hand on the right shoulder of a person wearing a white hat, left shoulder if they have a black hat. 29 should be able to correctly “guess” the color of their own hat. If a prison officer does the same for the one at the end of the line then all 30 will. Assuming all place their hands as agreed.

 

[qspeechc]

Hmm. I don't know bout that one. Not sure they'll be alowed to touch one another. I, personally, thought a solution would be more like guesses based on what the hats in front of you are. Or not.

 

[davee123]

Nobody ? :(

The 1st one's easy-- that one's been posted a bunch of times-- but the second one (if I understand it correctly) I'm having difficulty in proving. With *two* topics I can show it no problem (you need at least 6 scientists to guarantee a group of 3 discussing the same topic), but I can't seem to quite prove it with 3 topics.

The problem seems like it might be better stated as a geometry problem though, since I found it rather confusing to read. At first I thought the problem was asking "prove that at least 3 scientists are discussing the same topic", which is easy to prove. But as I started trying to prove it, I started thinking about it geometrically:

There are 17 points. Each point is connected to every other point by a line segment that is red, green, or blue. Prove that within these line segments, there exists a triangle that is made from the same color line segments.

DaveE

 

[qspeechc]

Yea, that would be a visual representation of the question.
I thought there might be a statistical way to prove it, but I can't think of any.

 

[davee123]

Acha! I have it! Explanation later!

DaveE

 

[davee123]

Ok. For the second problem, I'll build up the proof via reduction, using my 'colored lines' variation.

A) Assuming you have 3 points which must all be connected to each other, and only one color of line segment with which to connect them (red), it's obvious that this MUST form a triangle of a single color.

B) So. Let's assume you have 6 points to connect, and 2 colors of line segments (red, green). It can be shown that at least one of these points connects to 3 other points using the same color line segment-- let's say red. Therefore, the 3 points that it connects to CANNOT be joined by any red line segments, lest we create a red triangle. This leaves us to connect the 3 points using only ONE color, green, which will necessarily create a green triangle, as per A).

C) Now let's assume you have 17 points to connect, and 3 colors of line segments (red, green, blue). It can be shown that at least one of these points connects to 6 other points using the same color line segment (red). Then, none of these 6 points can be connected to each other using red, and thus must be connected to each other using only the two remaining colors. However, as per B), this is impossible without creating a triangle of a single color.

For, A), B), and C), it is trivial that for any number of points greater than or equal to the number of points given, but using the same number of colors, that the above will hold true. Hence, using 1 color, 3 or more points must form a triangle of a single color. Using 2 colors as per B), 6 or more points ensures a triangle of a single color. And using 3 colors as per C), 17 or more points ensures a triangle of a single color. Therefore, as the problem requests a proof for 17 points and 3 colors, we can prove that a single color triangle must exist within the set.


DaveE

 

[Tone.Tran]

My take on the first riddle.

If I take the prisoner at the back to be 1 and the prisoner in the front to be 30. Prisoner 1 being the one with nobody looking at his back.

Prisoner 1 would say prisoner 2's colour. This ensures Prisoner 2's survival. since Prisoner 2 is saved and couldn't save Prisoner 3, Prisoner 3 must go on to save the one in front of him. This means that there are 15 guaranteed saves.

I'm not 100% satisfied with this answer but it's the best that I've come up with, anyone have any better ideas?

 

[Kittel Knight]

My take on the first riddle.
...
I'm not 100% satisfied with this answer but it's the best that I've come up with, anyone have any better ideas?

Yes, read post #3.

 

[Tone.Tran]

Well, I was under the assumption they couldn't touch since qspeechc said that he/she wasn't sure they could touch.

 

[Rogerio]

It is not necessary to touch anyone:

From the last to the first in the line, each one says:
"I'm wearing" or "My color is" depending on the color of the next in the line.

 

[Tone.Tran]

Ah, awesome.

 

[michael5311]

If the prisoner at the back (number 30) is altruistic enough to save the prisoner in front of him (number 29) as described in post #12 then number 29 has a choice:

He can either use that information to save himself OR he can do the same favor for number 28.

Using that method at most 15 would be guaranteed survival (although a few more could get lucky by circumstance). post number 9 had it.

I think I remember there being a better solution but I don't remember what it was.

 

[davee123]

I'm suprised nobody has hunted down the answer on this one:


The prisoner who's last in line counts the number of white hats that he sees in front of him. If it's an odd number, he proclaims that his hat is white. If it's an even number, he proclaims that his hat is black. The next person in line then counts the number of white hats in front of him, and can deduce the color of his own hat. And so on down the line.

Hence, 29 of them are guaranteed to be saved, so long as all the prisoners follow the logic perfectly.


DaveE