Hey, this one is not that easy. not impossible, but not that easy either. it was asked for my lab partner in a job interview
there are 100 death row prisoners. the guards decided to execute them in the following way. they will make the prisoners sit in a row, and they will put a hat on each prison, either red or blue (colors doesn’t make a difference) then they will start from the prisoner sitting in the back , they will ask him what is the color of your hat, if he got it right they won’t shoot him, if wrong they will shoot him.
each prisoner can see all the prisoners in front of him and can hear all the prisoners before him and of course the gun shots.
now the prisoners were told that this is the way they will be executed, so they need to figure a plan to save the most number of prisoners. of course assume selflessness in all prisoners, so they all care about the overall number of saved prisoners.
very small hint: ALOT OF PRISONERS can be surely saved.