In how many ways can one fill a grid with a 0 or 1 in each square such that the sum of the entries in each row, column, and long diagonal is even?
HMMT February
Solution
First we name the elements of the square as follows: . We claim that for any given values of , and (the + signs in the diagram below), there is a unique way to assign values to the rest of the entries such that all necessary sums are even. Taking additions mod 2, we have , , , , . Since the 4th column, the 4th row, and the 1st column must have entries that sum to 0, we have , , . It is easy to check that the sum of entries in every row, column, and the main diagonal is even. Since there are ways to assign the values to the initial 8 entries, there are exactly 256 ways to fill the board.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.