King Hattius has \(n\) prisoners, when \(n\ge4\) is a positive integer, and is feeling generous since his court of Logicians did well at his daughter’s logic puzzle. This means he offers the prisoners a puzzle, and he’ll let them all free if at least one of them is correct.
He has lots of hats, coming in \(n\) different colours. He tells the prisoners that he’ll put a hat on each of their heads. They might all have different coloured hats, or some of the hat’s colours could be the same. The king tells them that they can see everyone else’s hat colour, but not their own, and that they’re not allowed to communicate once their hats are on. They all have to simultaneously guess the colour of their hat.
He does give them the chance to come up with a strategy before he puts their hats on. How would you help the prisoners escape?