Problem

Source:

Tags: IMO Shortlist, combinatorics, number theory, matrix



The rows and columns of a 2n×2n table are numbered from 0 to 2n1. The cells of the table have been coloured with the following property being satisfied: for each 0i,j2n1, the j-th cell in the i-th row and the (i+j)-th cell in the j-th row have the same colour. (The indices of the cells in a row are considered modulo 2n.) Prove that the maximal possible number of colours is 2n. Proposed by Hossein Dabirian, Sepehr Ghazi-nezami, Iran