Maths Olympiad Prep

Library / /490 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

In how many ways can one fill a 4×44 \times 4 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?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

First we name the elements of the square as follows: a11,a12,a13,a14,a21,a22,a23,a24,a31,a32,a33,a34,a41,a42,a43,a44a_{11}, a_{12}, a_{13}, a_{14}, a_{21}, a_{22}, a_{23}, a_{24}, a_{31}, a_{32}, a_{33}, a_{34}, a_{41}, a_{42}, a_{43}, a_{44}. We claim that for any given values of a11,a12,a13,a21,a22,a23,a32a_{11}, a_{12}, a_{13}, a_{21}, a_{22}, a_{23}, a_{32}, and a33a_{33} (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 a14=a11+a12+a13a_{14}=a_{11}+a_{12}+a_{13}, a24=a21+a22+a23a_{24}=a_{21}+a_{22}+a_{23}, a44=a11+a22+a33a_{44}=a_{11}+a_{22}+a_{33}, a42=a12+a22+a32a_{42}=a_{12}+a_{22}+a_{32}, a43=a13+a23+a33a_{43}=a_{13}+a_{23}+a_{33}. Since the 4th column, the 4th row, and the 1st column must have entries that sum to 0, we have a34=a14+a24+a44=a12+a13+a21+a23+a33a_{34}=a_{14}+a_{24}+a_{44}=a_{12}+a_{13}+a_{21}+a_{23}+a_{33}, a41=a42+a43+a44=a11+a12+a13+a23+a32a_{41}=a_{42}+a_{43}+a_{44}=a_{11}+a_{12}+a_{13}+a_{23}+a_{32}, a31=a11+a21+a41=a12+a13+a21+a23+a32a_{31}=a_{11}+a_{21}+a_{41}=a_{12}+a_{13}+a_{21}+a_{23}+a_{32}. It is easy to check that the sum of entries in every row, column, and the main diagonal is even. Since there are 28=2562^{8}=256 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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.