color the squares
Source: IMO Shortlist 1996, C2, Hungarian MO 2000, Italian MO 2008/2
July 2, 2007
geometryrectanglecombinatoricsColoringcountingIMO Shortlist
Problem Statement
A square (n \minus{} 1) \times (n \minus{} 1) is divided into (n \minus{} 1)^2 unit squares in the usual manner. Each of the vertices of these squares is to be coloured red or blue. Find the number of different colourings such that each unit square has exactly two red vertices. (Two colouring schemse are regarded as different if at least one vertex is coloured differently in the two schemes.)