How many squares of a 1000 x 1000 chessboard can be chosen, so that we cannot find three chosen squares with two in the same row and two in the same column?
Solution
Answer: 1998. Choose every square in the first row or column but not both.
We prove the slightly more general result that the maximum number for an m x n rectangle is n if m = 1, or m + n - 2 for m, n > 1.
We may assume m ≤ n. We use induction on m. The result for m = 1 is obvious. For m = 2, if we choose two in the same row, then we cannot choose any more, so it is better (or no worse for n = 2) to choose all the squares in a column giving n = m + n - 2 in total. That establishes the result for m = 1 and 2.
Now suppose n ≥ m > 2 and that the result is true for smaller m. We can certainly do at least m + n - 2 by choosing all the squares in the first row or column but not both. Assume we have m columns. If no two are in the same row, then there are at most n which we know is not optimal. So assume there are two in the same row. Now there cannot be any more in the two corresponding columns. So consider the remaining m-2 columns. If m > 3, then by induction we cannot choose more than m-2 + n - 2 in those columns and with the two already chosen that gives m + n - 2. If m = 3, then we cannot choose more than n in the remaining column. But we can combine at most n-1 of those with the existing two, since if we pick the square in the same row as the two squares already chosen, then we cannot choose any others. So for this case also we can do at most n+1 = m + n - 2. Hence the result is true for all m.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002