The 100 Prisoners Hat Puzzle - Solved

Welcome to The Puzzled Podcast, a show that explores the fascinating world of puzzles, riddles, and brain teasers. In each episode, we'll dive into a different puzzle, challenge, or mystery and explore the creative thinking and problem-solving skills required to solve it. Today's puzzle is named 'The 100 Prisoners Hat Puzzle'.

There are 100 prisoners in jail, all of whom have been sentenced to death. The jailer, who is feeling somewhat merciful, gives them a chance to go free if they can solve a puzzle. He explains the puzzle to the prisoners as follows:

"You will be placed in a room one by one, and each of you will be given a hat, either red or blue, chosen at random. You can see the hats of the prisoners who come before you, but not your own. Once you are in the room, you may not communicate with any other prisoner or leave the room. Then, you must guess the color of your own hat. If at least half of you guess correctly, you will all be set free. If not, you will all be executed."

The prisoners have one night to come up with a strategy. What strategy can they use to ensure that at least 50 of them go free?

Note: The hats are chosen independently for each prisoner, and there is no collusion between the prisoners beforehand. Also, the prisoners cannot communicate with each other in any way once they are in the room.