4n tokens on 4n*4n square
Source: Middle European Mathematical Olympiad 2013 I-2
May 17, 2014
combinatorics proposedcombinatorics
Problem Statement
Let be a positive integer. On a board consisting of squares, exactly 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 such that for any initial situation, we can do it in at most steps.