MEMO 2013 I2

Let $n$ be a positive integer. On a board consisting of $4n \times 4n$ squares, exactly $4n$ tokens are placed so that each row and each column contains one token. In a step, a token is moved horizontally of vertically to a neighbouring square. Several tokens may occupy the same square at the same time. The tokens are to be moved to occupy all the squares of one of the two diagonals. Determine the smallest number $k(n)$ such that for any initial situation, we can do it in at most $k(n)$ steps.