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?
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,000 problems in a working order, from AMC 10 level to the IMO shortlist.