Anche se probabilmente non interessa a nessuno, posto la mia soluzione per infiniti condannati:
Definizioni e imprecisioni varie(per far sembrare la soluzione pomposa. Se stai leggendo questo hai perso):
1) "Un prigioniero muore/non si salva/si sacrifica"= l'algoritmo NON garantisce la sua vita, ma potrebbe capitare che il colore detto corrisponde al proprio e quindi si salva
2) Sia $ \Omega $ l'insieme dei prigionieri che si salvano e $ \Psi $ di quelli che muoiono
3) Fatto su cui gira la dimostrazione: il primo prigioniero NON può dare l'informazione per tutti gli altri prigionieri (non solo considerando la somma: se ci fosse un altro modo, l'informazione data dal primo è limitata mentre l'informazione su "tutti" è infinita)
[Ovviamente se questo pseudo-assioma è falso crolla tutto]
4) Sia $ n $ il numero di prigionieri su cui il primo può dare/dà un informazione
5) Sia $ k $ il numero di colori
6) Sia $ N $ l'insieme dei prigionieri che NON ottengono l'informazione dal primo prigioniero .
Presuppongo di aver trovato un algoritmo funzionante. Distinguo tre casi:
1) $ \Psi $ è infinito
2) $ \Psi $ ha un solo elemento, ovvero il primo prigioniero.
3) $ \Psi $ ha più di un elemento, ma è limitato
Caso №1:
Banalmente, si può riutilizzare l'algoritmo per un numero di prigionieri limitato e fare in modo che il 1°, il $ (n+1) $°, il $ (n+2) $° si sacrifichino per dare l'informazione agli altri; in tal modo con $ n $ tendente a infinito $ \frac{|\Psi|}{|\Omega|} $ tende a $ 0 $.
Caso №2:
Siano $ X,Y \in N $ e $ a,b $ due "situazioni" (ovvero corrispondenza di colori per prigioniero) identiche tranne per $ X $ e $ Y $ (ovvero il colore del primo in $ a $ è uguale a quello del primo in $ b $, ecc.).
Notiamo che se esiste un siffatto algoritmo, tutti i prigionieri tranne $ X $ e $ Y $ diranno gli stessi colori, quindi in entrambi $ X_a $ può capire di trovarsi nel caso $ a $ solo grazie al colore detto dal 1°. Le possibili combinazioni di colori tra $ X $ e $ Y $ sono $ k^2 $, mentre il primo può dare un informazione per soli $ k $ casi, ovvero per il pigeonhole $ X $ e $ Y $ non possono capire in quale caso si trovano.
Caso №3:
Sia $ h $ il numero di prigionieri che si sacrificano. Prendiamo $ Z_1,Z_2,Z_3...Z_{h+1} \in N $. Analogamente al caso precedente, l'informazione data dai sacrificati "è" $ k^{h} $ mentre quella necessaria è $ k^{h+1} $, quindi questo caso non è possibile.
Spero sia corretta e decentemente comprensibile