O problema dos chapéus

O Luiz me mostrou esse vídeo que fala de uma variação do problema dos chapéus (o original ele já havia me mostrado antes).

Depois de tentar resolver e discutir soluções esbarrei num artigo fenomenal sobre esse tipo de problema, que generaliza os dois tipos de problema:
A Line of Sages - Tanya Khovanova - MIT - June 22, 2013 

O primeiro problema, pode ser resolvido matando sempre apenas no máximo 1 pessoa (a primeira, com 50% de chance). E vale para qualquer número de pessoas e de cores de chapéu (que podem ser convertidas em números de 1 a N). Existe também uma solução mais básica que salva metade sempre e a outra metade com 50% de chance. (Um truque para permitir somente a solução ótima é matar todos se houver mais de 1 erro, ou seja permitir no máximo 1 resposta errada)

O Segundo é uma variação do primeiro, só que adiciona a dificuldade do número de pessoas sempre ser igual ao número de cores de chapéu menos um e todos receberem chapéus diferentes. Além disso não permite repetição.
Esse tem 3 soluções interessantes (Obs: As duas primeiras soluções podem ser generalizadas para qualquer número de cores de chapéu - não precisa ser sempre um a mais que o numero de pessoas.):

-Uma parecida com a básica do problema anterior que salva metade e a outra metade com 50% de chance.
-Uma que mata no máximo 3 pessoas. Com chance de matar somente 2, 1 ou até mesmo nenhuma (Com bastante sorte).
-A melhor solução, que também consegue só matar no máximo 1 pessoa (a primeira).