June 24–June 30, 2008
Problem
Consider a rectangular array of dots with an even number of rows and an even number of columns. Color the dots, each one red or blue, subject to the conditions that in each row half the dots are red and half are blue, and in each column half the dots are red and half are blue. Now, if two points are adjacent (in either a row or column) and like-colored, join them by an edge of their color. Show that the number of blue segments is equal to the number of red segments.
Solution
There were some clever solutions via induction arguments and one with a nice matrix argument, but I'll give the short solution here.
List of solvers
Dustin Moody (graduate); Peiyush Jain, Rajneesh Hegde, Konrad Schroder, Lloyd Sakazaki, Kate Smith, Shyam Krishnamoorthy, Navdeep Jaitly (outside).
Navdeep Jaitly wins the prize!