2022/23 AHSMC Part 1 Problem 5

Problem 5 of 16

A $3 \times 3$ table of zeros and ones is called $2$ -avoiding if no row and no column has a sum of $2$ . For example, the table on the left is $2$ -avoiding (every row and column has a sum of $1$ ) but the table on the right is not (its first row has a sum of $2$ ). $\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \qquad \begin{array}{ccc} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}$ The total number of $2$ -avoiding tables with exactly $4$ , $6$ or $8$ ones is

Show solution

Solution

No such tables exist. If the table has $8$ ones, then there is exactly one zero and the row it is in has sum $2$ . Now suppose a table has $4$ ones. Then every row has a sum of $0$ , $1$ or $3$ (and similarly for the columns). Since there are three rows, there must be a row with sum exactly $3$ , say the first row. Similarly, there must be a column with sum exactly $3$ , say the first column. This implies the table has at least $5$ ones (so exactly $4$ ones is not possible). If the table has a sixth $1$ , then both the row and column it is in has sum $2$ . Therefore, there are no $2$ -avoiding tables with exactly $4$ , $6$ or $8$ ones. The answer is (E).

University of Alberta

Answer choices

Solution