Problem #3

Alternately color the squares of an a × b rectangle black and white beginning with black in the upper left-hand corner. If you are allowed to designate any subrectangle of the board and reverse the colors inside that rectangle, what is the minimal number of steps it takes to change all of the squares to black? For example, the figure below gives a non-minimal procedure which converts a 3 × 3 checkerboard to all black in four steps [the designated subrectangles are outlined in red].

Source: A generalization of a question from the USA Mathematical Olympiad

Back to the Archives

Back to the Math Department Homepage.