# Prison for the highly gifted

Everybody knows of the 'prison for the highly gifted'. It is the place full of criminals with inexplicably strong mental capabilities. For once, each of the inmates has the ability to memorise infinitely many points of data of any kind. Currently, there are a countable number of prisoners held at the prison. The guards decide to set up an experiment.

All prisoners are lined up in a row with a clear starting point, each prisoner facing the back of the prisoner in front of him/her. Each prisoner gets an arbitrarily chosen hat which can be either black or white; they do not know the colour of their own hat. They can only see the colour of the hats of all inmates in front of them (they have a telescopic vision of unseen caliber).
Starting with the first prisoner (which can see all other inmates), the guards ask him/her to name the colour of his/her hat. If the prisoner is correct, freedom is given to him/her. If the prisoner is incorrect, the guards shoot him/her. Either way, the guards walk up to the next prisoner and repeats the process. The prisoners are forbidden to communicate with each other in any way during the experiment. When asked the question, they may only answer with "black" or "white".
Before the whole experiment starts, the prisoners are given time to come up with a strategy together.

What strategy can they use, such that only a finite number of prisoners gets killed?

Source: Exercise $$21$$ of the course Logic.

All possible distributions of hats can be seen as elements of the set of rows with elements over the field $$\mathbb{F}_2$$, i.e. the set $$\mathbb{F}_2^\mathbb{N}$$. Define an equivalence relation on these elements: $$(x_n)_n \sim (y_n)_n$$ if and only if there exists an $$N \in \mathbb{N}$$ such that $$x_n = y_n$$ for all $$n \geqslant N$$. Using the infamous axiom of choice, each prisoner can remember a representative for each such equivalence class. Then, looking at the row of prisoners in front of him/her, the prisoner can derive to which equivalence class their hat distribution belongs and call the colour of his/her hat according to the corresponding class representative. In this way, it is possible that a finite number of prisoners will die, but, eventually, the hat distribution will match the class representative.

Note that we are not limited to two colours, but can even use a countable infinite number of colours.

Remarks? Want to submit your own solution? Don't hesitate to send me an email!