The problem: Each cell of an 8×8 chessboard is filled with either a 0 or a 1. Prove that if we compute the sums of the numbers in each row, each column, and each of the two diagonals, at least three of the sums must be equal.
I worked on this recently with some middle school students (aged 12, 13). It’s a good problem to chew on because it’s solvable but not too easy and it’s a bit of a challenge to write a clear and complete solution. My solution is below. Give the problem a try and compare your solution with mine.
To give you some distance from my solution, here are some backlit trees that live near my local library:
Solution:
Fact 1: we are talking about 18 sums: 8 rows + 8 columns + 2 diagonals = 18 sums
Fact 2: the value of each sum is a whole number in the range 0 to 8. The number of possible values is 9.
Observation: if the eighteen sums vary as much as possible, all different values from 0 to 8 are achieved, and they are achieved twice.
We wish to prove that: at least 3 of the 18 sums are equal. From the above observation, try a proof by contradiction.
Assume to the contrary: at most 2 sums are equal.
Because there are 18 sums, by the Pigeonhole Principle, we would have sums of 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8. This is equivalent to the original assumption that at most 2 sums are equal.
Observation: if a row sum is 0, the row has all zeroes. Similarly for columns.
Case 1: If one row and one column are the two 0-sums, then the chessboard would look like this: (without loss of generality, we can put the row of zeroes on top and the column of zeroes on left:)
00000000
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx
0xxxxxxx
However, in this configuration no sum of 8 (no row of 1s, no column of 1s, and no full diagonal of 1s) is possible. This contradicts the original assumption that at most 2 sums are equal.
Case 2: If two rows are zero, the chessboard looks like:
00000000
00000000
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
The sums of the columns and diagonals must have values from 1 to 6. This means that of the remaining rows, two must have values of 8 and two must have values of 7. This means that two columns have value at least 3, and six columns have value at least 4. The remaining rows have value 1, because the columns and diagonals cannot have value 1. The possibilities for the diagonals are at least 2 and 4, or 3 and 3. This means that the value of 2 can occur at most once, which contradicts the original assumption that 2 has to occur twice.
Case 3: If two columns are zero, use the same argument as Case 2, with rows and columns switched.
Case 4: If a row and diagonal are zero, no row, column, or diagonal can have value 8. This contradicts the original assumption.
Case 5: If a column and diagonal are zero, same argument as Case 4.
Case 6: If two diagonals are zero, same argument as Case 4.
Therefore at least 3 sums must be equal.