Some cells of a 2n x 2n board contain a white token or a black token. All black tokens which have a white token in the same column are removed. Then all white tokens which have one of the remaining black tokens in the same row are removed. Show that we cannot end up with more than n2 black tokens and more than n2 white tokens.
Solution
After the first move every column contains nothing but black tokens (and empty cells) or nothing but white tokens (and empty cells). After the second move the same applies to the rows. So let B be the number of rows containing a black token, and W be the number of rows with no black token. Similarly, let b be the number of columns containing a black token, and w the number of columns with no black token. Then B+W+b+w = 4n, so BWbw ≤ n4 (by AM/GM). Hence either Bb ≤ n2 or Ww ≤ n2. But the number of black tokens ≤ Bb (because only rows contain black tokens, and in each of those columns there are at most b black tokens). Similarly, the no. of white tokens is ≤ Ww.
© John Scholes
jscholes@kalva.demon.co.uk
20 December 2003