let us say that R(n) is the number of red hats that student at position n can see, and B(n) the number of blue hats. S(n) is the announcement that student at position n makes.
either R(20) or B(20) is odd (as the student at the back of the line can see 19 other students). if R(20) is odd then S(20) = "red", if B(20) is odd then S(20) = "blue" - the student at the back will announce the oddness of one or the other colour, and forfit his own freedom.
now, consider student 19. he can see R(19) and B(19), and he knows which of R(20) or B(20) was odd. if R(20) was odd, and R(19) even, he must have a red hat on. if R(20) was odd, and R(19) is still odd, he must have a blue hat on. so he can safely announce which colour hat he has.
student 18 can take the information about the oddness of R(20) and B(20) and take into account the annoucement of S(19), and work out whether either or both of R(19) or B(19) was odd. by comparing these values with the oddness of R(18) and B(18), they can work out their own hat colour.
i don't think there's anything the professor can do to stop this, and they can work indctively down the line.
so the optimal solution allows 19 of the 20 students to go free.
Slashdot Mirror
www.beholder.co.uk/planetarium/ is my favourite mathematical/logical/linguistic puzzle. it takes a bit of solving, mind.
from my experience of maths professors, the puzzle as posed was already a real world situation =)
oops. sorry. didn't see the instuction about not posting solutions. i'll delete it if someone tells me how?
let us say that R(n) is the number of red hats that student at position n can see, and B(n) the number of blue hats. S(n) is the announcement that student at position n makes. either R(20) or B(20) is odd (as the student at the back of the line can see 19 other students). if R(20) is odd then S(20) = "red", if B(20) is odd then S(20) = "blue" - the student at the back will announce the oddness of one or the other colour, and forfit his own freedom. now, consider student 19. he can see R(19) and B(19), and he knows which of R(20) or B(20) was odd. if R(20) was odd, and R(19) even, he must have a red hat on. if R(20) was odd, and R(19) is still odd, he must have a blue hat on. so he can safely announce which colour hat he has. student 18 can take the information about the oddness of R(20) and B(20) and take into account the annoucement of S(19), and work out whether either or both of R(19) or B(19) was odd. by comparing these values with the oddness of R(18) and B(18), they can work out their own hat colour. i don't think there's anything the professor can do to stop this, and they can work indctively down the line. so the optimal solution allows 19 of the 20 students to go free.