Q12 Matemática  (Balkan MO Shortlist 2013)

As células de um tabuleiro de xadrez $n\times n$ são coloridas em várias cores, de modo que nenhum quadrado $2\times 2$ contém quatro células da mesma cor. Um caminho próprio de comprimento $m$ é uma sequência $a_1,a_2,...,a_m$ de células distintas em que as células $a_i$ e $a_{i+1}$ têm um lado comum e são coloridas em diferentes cores para todos os $1\le i<m$. Mostre que existe um caminho próprio de comprimento $n$.