Q5 Matemática  (IberoAmerican 2019)

Don Miguel coloca uma ficha em um dos vértices $(n+1{)}^2$ determinados por um tabuleiro $n\times n$. Uma jogada consiste em mover a ficha do vértice em que está colocada para um vértice adjacente que esteja no máximo a $\sqrt{2}$ de distância, desde que permaneça no tabuleiro. Um caminho é uma sequência de movimentos tal que o token estava em cada um dos vértices $(n+1{)}^2$ exatamente uma vez. Qual é o número máximo de movimentos diagonais (aqueles de comprimento $\sqrt{2}$) que um caminho pode ter no total?