Brain teaser

[OpenGL guy]

My niece asked me this one earlier and my response was that there is no solution... tell me what you think.

There are three students and five hats (two are red and three are blue). A teacher has the students closer their eyes while she hides two of the hats and places the remaining hats on the students' heads. A student may open their eyes and choose to guess what color hat is on their head (wrong answers are punished with extra homework, so you won't guess unless you can be sure).

Student 1 opens his eyes and passes.
Student 2 opens her eyes and passes.
Student 3 correctly guesses the color of her hat without opening her eyes.

What color was the third student's hat and how did they deduce it?


My thoughts...
There are three possibilities for the three remaining hats on the student's heads:
1) 3 blue hats
2) 2 blue and 1 red hat
3) 1 blue and 2 red hats

Now, if case 1, I submit that no student could have guessed the color of their own hat. The reason being that they would open their eyes and see two blue hats... no way to know if their hat is blue or red.

In case 2, again, I submit that no student could have guessed the color of their hat. The reason being that they would see either two blue hats or one red and one blue. No way to determine what color their own hat was.

In case 3, any student that sees two red hats would know they had a blue hat (since all red hats would be visible). If student 1 saw two red hats, they would have said blue, but they passed so they must have seen one of each color. Ditto for student 2. Thus student three could have guessed blue if they opened their eyes.

I see no way to eliminate cases 1 and 2. So my take is that the problem is flawed, or my niece didn't relate the problem well (it was over the phone).

Other ideas?

 

[K.I.L.E.R]

Does she still go to primary school?

If so, the answer is:
The first 2 students peaked while the teacher was putting their hats on and the 3rd student peaked when the teacher got the hat she is going to put on the 3rd student.

 

[Althornin]

Ok.

There are only two ways student 1 would have passed:
IF he saw 2 blue hats or one blue and one red hat.
IF he saw two red hats, he knows his is blue.

Ok.
So enter student 2
He now knows that if student 3 has a red hat, then his own hat MUST be blue.
Because he passed, we now know that student 3's hat must be blue - and so, student 3 can answer without even looking!

 

[CI]

Read a very similar question the other day:

There are 3 guys: A, B and C.
A, B, and C each has a hat on his head.
A and B can't see what color is their own hat, but they can see the color
of other people's hat.
C is blind so can't see anything.
They all have been told that there are 3 red hats and 2 white hats.
Three of these 5 hats are on their heads, and they can't see the other 2
hats.
A says: "I can't tell what color my hat is."
B says: "Neither can I."
C says: "I can."
What color is C's hat and how did he know?

Only diff is the change in color from Red to Blue and White to Red.

Ambiguity arises when the first 2 students open their eyes and sees one red and one blue hat each. Therefore, the third student could deduce that that she's wearing a blue hat without looking since both red hat's worn by the first two. So it's option 3.

 

[Althornin]

Ambiguity arises when the first 2 students open their eyes and sees one red and one blue hat each. Therefore, the third student could deduce that that she's wearing a blue hat without looking since both red hat's worn by the first two.

ah, but this is wrong.
Student one could open his eyes and see students 2 and 3 wearing blue hats. he must pass.
Then student two could see that student 3 has a blue hat and student 1 has a red OR blue hat. Doesnt matter.

The thing is, color of student 1 and 2's hats are irrelevant. Both could be red, both could be blue, and one could be each. it works any way you do it.


To further explain and show OGL Guy where hie made his mistake:

Now, if case 1, I submit that no student could have guessed the color of their own hat. The reason being that they would open their eyes and see two blue hats... no way to know if their hat is blue or red.

In case 2, again, I submit that no student could have guessed the color of their hat. The reason being that they would see either two blue hats or one red and one blue. No way to determine what color their own hat was.

In case 3, any student that sees two red hats would know they had a blue hat (since all red hats would be visible). If student 1 saw two red hats, they would have said blue, but they passed so they must have seen one of each color. Ditto for student 2. Thus student three could have guessed blue if they opened their eyes.

you keep neglecting the extra information that each successive student recieves.
Case 1:
3 blue hats:
Student 1: Sees two blue hats, cannot guess
Student 2: Sees two blue hats, knows that his and student 3's hat must be either 1 red, 1 blue OR both blue. students 3's hat is blue, so his can be either red or blue. he must pass.
Student 3: The only reason student 2 would have passed would be if student 3's hat was blue, ergo, puzzle solved.

Case 2:
1 red, two blue hats
Student 1: Sees a red hat on student 2 and a blue hat on student 3
Student 2: Sees two blue hats. knows that his and student 3's hat must be either 1 red, 1 blue OR both blue. students 3's hat is blue, so his can be either red or blue. he must pass.
Student 3: The only reason student 2 would have passed would be if student 3's hat was blue, ergo, puzzle solved.

Case 3:
2 red ahts, one blue hat
Student 1: Sees a red hat on student 2 and a blue hat on student 3
Student 2: Sees a red hat on student 1 and a blue hat on student 3. knows that his and student 3's hat must be either 1 red, 1 blue OR both blue. students 3's hat is blue, so his can be either red or blue. he must pass.
Student 3: The only reason student 2 would have passed would be if student 3's hat was blue, ergo, puzzle solved.

 

[Nathan]

A slightly shorter proof

If we assume student 3's hat is red, then 1 must have seen red and blue hats, which isn't enough info for her to know what colour her hat is. 2 sees at least one red hat, which means her hat could not be red because 1 would have seen two red hats and been able to deduce that hers was blue. Since 2 didn't guess, 3's hat can't be red.

edit: Whoops, didn't see Althorin's first answer

 

[DemoCoder]

Try this one:

Gilgameshl invades a village of smurfs and announces that he's going to kill and any who don't pass his test. He says he will return the next day, line all of the smurfs up single file (there are 100 smurfs) and put hats of either red or blue on each of them. Each smurf in turn must call out "red" or "blue" and any smurf who does not call his own hat color correctly gets
killed.

Each smurf can hear the answers of any other smurf and see the hat color of all smurfs in front of them in line. Each smurf can only say "red" or "blue".

The smurfs get together that night and plan an optimal strategy for saving the maximum number of smurfs. How many can be saved, and how?

An obvious, but non-optimal strategy, for example, is for the smurfs to agree that every other smurf calls out the color of the person in front of them. Smurf 1 says color of Smurf 2, Smurf 2 says whatever Smurf 1 said, Smurf 3 says what Smurf 4 has, etc. Worst case, 50% are saved.



Or another one:
You are given a write once memory with 7 bits. That is, once a '1' bit is written to a position, it cannot be changed. How can you write a 3-bit number (integers 0-7) 4 times into this memory? For example, I want to write the numbers 5, 2, 6, 3 into this memory. After each write, I should be able to read the number back unambiguously.

(hehe, don't even try to find the last one on the internet. It's from a very old combinatorics paper that I haven't found anywhere on the net)

 

[K.I.L.E.R]

How about this:

You have a 16 dimensional array, illustrate 16 dimensions with a picture.

 

[Simon F]

Try this one:

Gilgameshl invades a village of smurfs and announces that he's going to kill and any who don't pass his test. He says he will return the next day, line all of the smurfs up single file (there are 100 smurfs) and put hats of either red or blue on each of them.

Assuming this is the same as a puzzle I've already seen (and solved) I think you should also mention that everyone in the line faces the same direction so that the smurf at the start can see no other smurfs and the smurf at the end can see everyone else.

Or another one:
You are given a write once memory with 7 bits. That is, once a '1' bit is written to a position, it cannot be changed. How can you write a 3-bit number (integers 0-7) 4 times into this memory? For example, I want to write the numbers 5, 2, 6, 3 into this memory. After each write, I should be able to read the number back unambiguously.

Assuming you don't have to read Number N after writing N+1, then this seems simple enough. It took me about 2 minutes to solve. I won't write my solution since it'll give someone else a chance. [EDIT] Damn. Just realised I'd missed a case[/EDIT]

OK here's another one. Re-using the Smurfs, Gilgamesh re-invades and tells the smurfs he's going to magically mark all the "sinners" in the town with a spot on their foreheads.[EDIT] They are told there is at least one sinner[/edit] Sinners must leave the village. There are no mirrors in smurfland and everyone is far too polite to mention an embarassing mark on someone else's forehead. Everyday, every smurf sees everyone else.

At the end of the fourth day, all the sinners have left. How many were there?

 

[DemoCoder]

The solution to the write once problem, atleast the elegant one, uses projective planes (e.g. the projective plane of order 2: The Shannon/Fano plane)


There might be others, just like with the "N-weighings, find bad coin" problems, but I find the information theory/combinatorics/coding theory solutions to be the most appealing.


Simon, I think your problem is missing something. It must be known that there is atleast one sinner, or marked head.

Day 1: If there were exactly one sinner, than one of the smurfs would see that all of the others had no marks, and therefore conclude he is a sinner. Since he didn't, there must be more than one sinner.

Day 2: If there were exactly two sinners, than a smurf that didn't know on Day 1 would see that there is one smurf that is marked, and therefore conclude he is a sinner as well. SInce he didn't, there is more than two.

Day 3: Same reasoning, if som esmurf saw exactly 2 other sinners, conclude that since they didn't know on day 1 and 2, then he must be sinner. Therefore, there must be more than 3.

Day 4: Sinner smurfs each see 3 other sinners. They conclude there must be exactly 4 sinners.

 

[K.I.L.E.R]

I'm trying to make a point guys.

The moment you are capable of doing as I have requested a few posts above with the dimensions, then you will be able to answer all these other inane riddles.

 

[Simon F]

I'm trying to make a point guys.

The moment you are capable of doing as I have requested a few posts above with the dimensions, then you will be able to answer all these other inane riddles.

Prove it.

Have you ever worked on a problem in 16 dimensional space? FWIW the DC VQ compressor does.

 

[Simon F]

Simon, I think your problem is missing something. It must be known that there is atleast one sinner, or marked head.

You spotted the deliberate mistake then (I should know better than to just go from memory!)

As for your "7bit" problem, I did combinatorics a loooong time ago and don't recall anything about Shannon Projective Planes.

I'll post another puzzle in a little while (as soon as I've remembered it correctly )

 

[Althornin]

Day 1: If there were exactly one sinner, than one of the smurfs would see that all of the others had no marks, and therefore conclude he is a sinner. Since he didn't, there must be more than one sinner.

Day 2: If there were exactly two sinners, than a smurf that didn't know on Day 1 would see that there is one smurf that is marked, and therefore conclude he is a sinner as well. SInce he didn't, there is more than two.

Day 3: Same reasoning, if som esmurf saw exactly 2 other sinners, conclude that since they didn't know on day 1 and 2, then he must be sinner. Therefore, there must be more than 3.

Day 4: Sinner smurfs each see 3 other sinners. They conclude there must be exactly 4 sinners.

this bit makes zero sense.

 

[Xmas]

Try this one:
Or another one:
You are given a write once memory with 7 bits. That is, once a '1' bit is written to a position, it cannot be changed. How can you write a 3-bit number (integers 0-7) 4 times into this memory? For example, I want to write the numbers 5, 2, 6, 3 into this memory. After each write, I should be able to read the number back unambiguously.

That seems to be only possible if the sequence of numbers is known beforehands.

 

[DemoCoder]

Day 1: If there were exactly one sinner, than one of the smurfs would see that all of the others had no marks, and therefore conclude he is a sinner. Since he didn't, there must be more than one sinner.

Day 2: If there were exactly two sinners, than a smurf that didn't know on Day 1 would see that there is one smurf that is marked, and therefore conclude he is a sinner as well. SInce he didn't, there is more than two.

Day 3: Same reasoning, if som esmurf saw exactly 2 other sinners, conclude that since they didn't know on day 1 and 2, then he must be sinner. Therefore, there must be more than 3.

Day 4: Sinner smurfs each see 3 other sinners. They conclude there must be exactly 4 sinners.

this bit makes zero sense.

No, it makes perfect sense. On the first day, if there were exactly one smurf with a painted head, then the smurf with the painted head would instantly know it (since it is known by all smurfs that there must ATLEAST be one). Thus, this smurf would leave. Therefore, there must atleast be two smurfs with painted heads. Each smurf can conclude this on the second day from the fact that no smurf's were able to determine their status.

Let's say there were exactly two.

on Day 2, the smurfs with painted heads would see each other (i.e. that there is one other smurf with a painted head) . Let's call them A and B.

A can see that B's head is painted and B can see A. A knows that B wasn't able to determine his status on Day 1, therefore he knows that B can see atleast one other painted head. Since A cannot see any other smurfs besides B with painted heads, he can conclude that he has the painted head.

Just keep applying the same reasoning iteratively everyday.

 

[OpenGL guy]

Ok.

There are only two ways student 1 would have passed:
IF he saw 2 blue hats or one blue and one red hat.
IF he saw two red hats, he knows his is blue.

Ok.
So enter student 2
He now knows that if student 3 has a red hat, then his own hat MUST be blue.
Because he passed, we now know that student 3's hat must be blue - and so, student 3 can answer without even looking!

Thanks, that's exactly what I was missing.

 

[Althornin]

[
No, it makes perfect sense. On the first day, if there were exactly one smurf with a painted head, then the smurf with the painted head would instantly know it (since it is known by all smurfs that there must ATLEAST be one). Thus, this smurf would leave. Therefore, there must atleast be two smurfs with painted heads. Each smurf can conclude this on the second day from the fact that no smurf's were able to determine their status.

Let's say there were exactly two.

on Day 2, the smurfs with painted heads would see each other (i.e. that there is one other smurf with a painted head) . Let's call them A and B.

A can see that B's head is painted and B can see A. A knows that B wasn't able to determine his status on Day 1, therefore he knows that B can see atleast one other painted head. Since A cannot see any other smurfs besides B with painted heads, he can conclude that he has the painted head.

Just keep applying the same reasoning iteratively everyday.

arg!
i was not thinking that there had to be at least one smurf with a mark, and was thus stupified by the first step. Of course, i just re-read your post and determined that you said he left that out. Thanks for the good explaination though.

 

[Simon F]

Day 1: If there were exactly one sinner, than one of the smurfs would see that all of the others had no marks, and therefore conclude he is a sinner. Since he didn't, there must be more than one sinner.

Day 2: If there were exactly two sinners, than a smurf that didn't know on Day 1 would see that there is one smurf that is marked, and therefore conclude he is a sinner as well. SInce he didn't, there is more than two.

Day 3: Same reasoning, if som esmurf saw exactly 2 other sinners, conclude that since they didn't know on day 1 and 2, then he must be sinner. Therefore, there must be more than 3.

Day 4: Sinner smurfs each see 3 other sinners. They conclude there must be exactly 4 sinners.

this bit makes zero sense.

But it's the correct solution. [EDIT Oops sorry about leaving out the "at least one sinner" bit]

 

[Simon F]

Puzzle 2:

There is a bell tower in a church. Two ropes are hanging down through small holes in the ceiling but the bell mechanism has long since corroded up and so the ropes/bells don't move. A thief wants to steal some rope. [Apparently he's heard that there's money for old ...(sorry)]

The ceiling is 50 metres off the floor, the walls and ceiling of the tower are perfectly smooth, and the ropes are 1 metre apart. The ropes hang vertically and reach all the way to the floor. The thief is an expert at rope climbing etc, can safely land after a fall of 3 metres, and is equiped only with a knife.

Approximately how much rope can he steal?