OIM 2025 Problem 6

Um sultão capturou 23 magos e propõe um jogo para libertá-los. O sultão diz que vai construir 11 poços numerados de 1 a 11 e uma torre. Dentro de cada poço colocará dois magos e colocará o último na torre. Em cada mago nos poços colocará um chapéu de uma entre quatro cores (conhecidas por todos) e no da torre colocará um chapéu de uma entre 2025 cores (distintas das outras 4 e conhecidas por todos).

Nenhum mago saberá a cor do seu chapéu. Depois de ser colocado no poço, cada mago saberá o número do poço em que está, além disso, verá unicamente o chapéu do mago da torre e o do seu companheiro de poço. O mago da torre conhecerá o número de cada poço e poderá ver os chapéus de todos os outros magos. Num determinado momento, o sultão dará uma ordem e, simultaneamente, cada mago dirá: «A cor do meu chapéu é $x$», onde «$x$» é uma cor. Se pelo menos um mago diz uma frase verdadeira, todos os magos ganham e ficam livres, em outro caso, perdem.

Antes de serem postos nos seus lugares e de receber os seus chapéus, os magos terão à disposição um tempo para combinar uma estratégia, mas não poderão comunicar entre si depois disto. Os magos poderão assegurar a vitória, independentemente do que o sultão faça?