The Setup

The reason this has started popping up again in articles on Facebook, Twitter, and other social media networks, is because as of recently Google‘s artificial intelligence (AI) has put together an algorithm that solves the riddle. Essentially, the AI, labelled as Google Deepmind, is smart enough to work for Google.

I find this intriguing because a few years back I was flown out to Google’s offices for a tour and interview for a UX position. During the interview, I was posed with this exact riddle. After the time I was given expired, I did end up solving it, but the answer I came up with in the end, wasn’t the first one I came up with. My background, as some may know, is mainly web development now. I love problem solving and because of that, I took to programming because that is the way my brain works. When I was given this riddle, that’s essentially how I solved it. I treated is as a problem that I could solve with code. I’ll talk about the process I went through right away, but first…

The Riddle

An executioner lines up 100 prisoners single file and puts a red or a blue hat on each prisoner’s head. Every prisoner can see the hats of the people in front of them in the line, but not their own hat, nor those of anyone behind them.

The executioner starts at the end (very back of the line) and asks the last prisoner the color of their hat. They must answer “red” or “blue”. If they answer correctly, they are allowed to live. If they gives the wrong answer, they are killed instantly and silently. While everyone hears the answer, no one knows whether an answer was correct.

On the night before the lineup, the prisoners confer on a strategy to help them. At this time there is no indication of how many blue or red hats used. What should they do?

Can You Solve It?

So, you read the riddle. Take some time. See if you can figure it out. Don’t read ahead if you want to give it a try. I’m going to outline what I came up with below.

My Results

So, my first line of thinking was to have every person call out the color of the hat in front of them. Not a bad plan… but statistically it only saves roughly 75% of the people in the line. There is a better way.

I tend to work visually. So, what did I do? I scribbled.

I drew a bunch of little circles on paper and gave each of them one of two colors. Red or blue. Then I sat… and stared… and worked out random ideas in my head. Essentially, I just brainstormed with myself as I usually do with any problem. I played with the idea of the modulo operation or modulus (finding the remainder of division) by taking the sum of one color divided by the sum of the other and tried that while moving to each circle in the lineup. Then I tried the same thing but with the number of people divided by one color and then the other. This put me on the right track with the odd or even thinking because the results of modulus, at least when I was taught about it, were used in some of our examples to figure out if something was odd or even. For example, taking a number dividing it by 2 would either give the remainder of 0 or 1. If it was 0, the number was even, if it was 1, the number was odd. And here is where I found my solution. Don’t ask me how I jumped from one idea to next, I really don’t know. My brainstorming is sporadic. One train of thought could all of a sudden jump to something completely unrelated because of one single word that ran through my head. If you followed my thinking, great! Anyways! You probably don’t really care how I got to the answer, you just want the answer. So…

We have to set up a system where we use odd and even counts when looking at the hats. We have to have every person count the number of a selected color in front of them. This color should be decided the night before. So, let’s say red is the color we decided on. The very first person will count the number of red hats in front of them. If there is an odd amount of red hats the person calls out RED! If there is an even amount of red hats, the person will call out BLUE! Everyone else will need to listen to this first prisoner. They let everyone know how many are in the entire line up, minus them self. They could be a sacrifice. They have a 50/50 chance of living, but either way, will save the rest of the people in the lineup.

You with me so far? See where I’m going with this?

Now each prisoner just has to worry about what color hat they themselves are wearing. To figure this out, as their turn comes up, they have a few things to keep track of. First, the original count of red hats (odd or even). Second, how many red hats were called out behind them. And lastly, how many are left in front of them. Using these three bits of information, they should be able to accurately figure out the color of their own hat.

The Test

Variables

Amount of prisoners in the lineup = 10

Amount of red hats in the lineup = 5

Amount of blue hats in the lineup = 5

The Algorithm

Here’s the lineup for this example. Number 10 being the last person in the lineup.

Prisoner 10 aka the last person in line takes a look ahead. They see that there are 4 red hats. They follow the plan and call out BLUE! Unfortunately, they could be the sacrifice… and in this case, they were. They are executed. Everyone else in the lineup makes note. They now know that there are an even amount of red hats among the remaining 9 prisoners.

Now, every remaining person only has to worry about the hat they are wearing. To figure that out they just have to count the amount of red hats in front of them and keep track of how many showed up behind them with the exception of prisoner 10. Prisoner 10 isn’t part of the count for hats behind.

Prisoner 9: 4 red hats in front of them. Even. They call out BLUE!

Prisoner 8: 3 red hats in front of them plus 0 red behind them. That makes the red count odd. The person behind them saw an even number meaning they must be wearing one of the red hats. They call out RED!

Prisoner 7: 3 red hats in front of them plus 1 red behind them. That makes the count even. They must be wearing a blue, so they call out BLUE!

Prisoner 6: 2 red hats in front plus 1 red behind them. That makes the count odd. They must be wearing a red, so they call out RED!

Prisoner 5: 1 red hat in front plus 2 hats behind. Odd. They call out RED!

Prisoner 4: 1 red hat in front plus 3 hats behind. Even. They call out BLUE!

Prisoner 3: 1 red hat in front plus 3 hats behind. Even. They call out BLUE!

Prisoner 2: 0 red hats in front plus 3 hats behind. Odd. They call out RED!

Prisoner 1: 0 red hats in front plus 4 behind. Even. They call out BLUE!

Don’t get me wrong, there are some issues that could arise but for the sake of the riddle we ignore them. What if the last person in the line can’t see to the front of the line (they can’t count how many red hats there are)? What if some people in the line are terrible at math. What if one person screws up? All of these throw this plan right out the window.

If my explanation doesn’t make sense, I found another site that explains it here: puzzles.nigelcoldwell.co.uk/thirtynine.htm

And No…

I was offered the position, but I didn’t end up taking it. I flew down to see what it was all about but at the time there were too many factors involved. After weighing all my options, I ended up passing on the position and stayed in Saskatoon. I know, I know… what an idiot, passing a job at Google! Trust me, that same thought ran through my head over and over again. Looking back now though, I’m glad I made the decision I did. I started up my own company, made a ton of great friends in Saskatoon, and on occasion get to travel with a friend, who I now consider family, and his bandmates helping them out as Tour Manager. Those experiences have been amazing and I wouldn’t give them up for anything, even a job with what I hear is the best company to work for.