Useful video links with Questions and Answers(.NET, SQL/Database, Azure, DSA, Docker, GIT, AI)

Most of us have a habit of solving puzzles and riddles in newspapers and other magazines. In fact, we take it as a challenge and will try it very hard to solve them. For all those riddle lovers, here is a riddle used during job interviews for Goldman Sachs and Google.So here goes the riddle, give some work to your brain and solve this:

• There are 100 prisoners lined up by an executioner, who places either a red hat or blue hat upon each of their heads.
• Prisoners can’t look at their own hat and the hats of the people who are behind them but they can see the hats of the people who are lined up in front of them.
• Starting from the back, executioner asks the last prisoner about the colour of his own hat.
• In order stay alive, the prisoner must give the correct answer. If he doesn’t, he will be killed ‘instantly and silently’.
• This indirectly mean other prisoners will hear the answer but will not know whether it is correct or not.
• The night before the line-up, all the prisoners can discuss a plan to save themselves.

What should they do to save themselves?

Tried it?

Not getting?

Can’t solve?

Okay then here is the answer:

Here is the best strategy to save 99 prisoners with 100% certainty, while the remaining 1 prison has a 50-50 chance of survival.

To implement the above plan successfully, all the prisoners must agree to a communication protocol. The first prisoner to speak (last in line) will say ‘blue’ if there are ‘EVEN number’ of blue hats in front of him else he will say ‘red’ (i.e if there are ‘ODD number’ of blue hats).

With the responses they have heard behind, rest of prisoners will get an idea about their own hat colours based on the hats they see in front of them.

In this way, everyone except the first prisoner will definitely get the correct answer and the first person will have 50-50 chances of the correct answer.
DETAILED EXPLANATION BY AUTHOR AFTER READING COMMENTS:-

100 Prisoners are standing in a line
Let’s say 100th prisoner finds number of blue hats in front of him are EVEN so he replies with BLUE
All other prisoner hears that 100th prisoner said Blue. Means out of first 99 hats, blue hats are even.
Now 99th prisoner gets chance to tell color of his hat. He counts the hats in front of him. If he sees Blue hats are EVEN in front of him then it means he is wearing Red hat. If he sees Blue hats are odd in front of him then it means he is wearing Blue hat. Let’s say Blue hats are even in front of him, it means he is wearing Red hat, so he speaks Red and got saved.

Now 98th prisoner knows that 100th prisoner said BLUE (out of first 99 hats, blue are even) & 99th prisoner said Red and he got saved. Now if 98th prisoner sees number of blue hats in front of him to be odd then it means he is wearing Blue because 99th prisoner was wearing Red and he already knows about it.
If 99th prisoner would have said BLUE then 98th prisoner should consider that in his calculations accordingly. In that case, if number of blue hats in front of 98th prisoner are odd then it means he is wearing red coz 100th prisoner saw EVEN blue hats in front of him and one blue hat was on 99th prisoner and remaining ODD blue hats in front of 98th. Means 98th cannot wear Blue.
These combinations needs to be remembered by 1st prisoner and all remaining 99 prisoners can get saved.

Few people are commenting that every prisoner should tell the color of hat in front of him to save people in front of him. This is so wrong as it is practically not possible to tell.
For eg if 100th Red, 99th Blue, 98th Red
Then 100th one will say Blue to save 99th prisoner. Now 99th prisoner hears that Blue and he thinks he is wearing blue but he sees prisoner in front of him is wearing Red. If 99th says blue then he will get saved but 98th prisoner will never come to know whether 99th prisoner was killed or not.

Do you have any other solution of this riddle? Were you able to solve this riddle? If yes then how many minutes did you take? Share in comments section below.