Maths Olympiad Prep

Library / /7 of 7

Combinatorics Difficulty 5.3 AIME, harder Prove it Hong Kong

There is a 3×33 \times 3 table and 99 cards printed with the numbers 4-4, 3-3, 2-2, 1-1, 00, 11, 22, 33, 44. How many ways are there for these cards to be distributed to the cells of the table so that there is one card in each cell, and that the sum of the numbers of the three cards on each row, each column and each of the two diagonals of the table is nonnegative?

Solution

Answer: 3232

We first make a few observations.

* The sum of the numbers on all cards is 00. Hence each row sum being nonnegative is equivalent to each row sum being 00.
* For the same reason as above, each column sum must be 00.
* The card 4-4 cannot be placed in a corner cell. Indeed, if 4-4 is placed in a corner cell as shown below, then the sum of the other two numbers in the first row is 44, the sum of the other two numbers in the first column is 44 and the sum of the other two numbers in the diagonal containing 4-4 is at least 44. This is impossible since the sum of the positive numbers on the cards is only 1+2+3+4=101 + 2 + 3 + 4 = 10.

Figure 1

* In essentially the same way we can prove that the card 4-4 cannot be placed in the central cell.

From the above observations, there are 44 choices for the position of 4-4. After the position of 4-4 is fixed as shown below, there are 44 choices for the other two numbers in the first row (we either put in {0,4}\{0, 4\} or {1,3}\{1, 3\} in either order), and then 22 choices for the other two numbers in the second column (we put in the remaining pair in either order).

4×4×2=324 \times 4 \times 2 = 32

ways to fill in five cells. There is then only one way to fill in the remaining cells using the numbers 3-3, 2-2, 1-1 and 22. For instance, suppose we have filled the cells in the following way, with aa, bb, cc, dd denoting the numbers yet to be filled in:

<table><tr><td>1</td><td>-4</td><td>3</td></tr><tr><td>a</td><td>0</td><td>b</td></tr><tr><td>c</td><td>4</td><td>d</td></tr></table>

By considering the rows, we need a+b=0a + b = 0 and c+d=4c + d = -4, so {a,b}={2,2}\{a, b\} = \{2, -2\} and {c,d}={1,3}\{c, d\} = \{-1, -3\}. By considering the columns, we need a+c=1a + c = -1 and b+d=3b + d = -3. Hence the only possibility is (a,b,c,d)=(2,2,3,1)(a, b, c, d) = (2, -2, -3, -1). It remains to check whether these 3232 ways also satisfy the requirement that the two diagonal sums are nonnegative. We start with the following 44 cases with the position of 4-4 fixed:

<table><tr><td>1</td><td>-4</td><td>3</td></tr><tr><td>2</td><td>0</td><td>-2</td></tr><tr><td>-3</td><td>4</td><td>-1</td></tr></table>

<table><tr><td>1</td><td>-4</td><td>3</td></tr><tr><td>-3</td><td>4</td><td>-1</td></tr><tr><td>2</td><td>0</td><td>-2</td></tr></table>

<table><tr><td>0</td><td>-4</td><td>4</td></tr><tr><td>2</td><td>1</td><td>-3</td></tr><tr><td>-2</td><td>3</td><td>-1</td></tr></table>

<table><tr><td>0</td><td>-4</td><td>4</td></tr><tr><td>-2</td><td>3</td><td>-1</td></tr><tr><td>2</td><td>1</td><td>-3</td></tr></table>

All cases have both diagonal sums being nonnegative. The other 44 cases with 4-4 in the same position must therefore also have the same property, since they are obtained by swapping the first and third columns from the 44 cases above:

<table><tr><td>3</td><td>-4</td><td>1</td></tr><tr><td>-2</td><td>0</td><td>2</td></tr><tr><td>-1</td><td>4</td><td>-3</td></tr></table>

<table><tr><td>3</td><td>-4</td><td>1</td></tr><tr><td>-1</td><td>4</td><td>-3</td></tr><tr><td>-2</td><td>0</td><td>2</td></tr></table>

<table><tr><td>4</td><td>-4</td><td>0</td></tr><tr><td>-3</td><td>1</td><td>2</td></tr><tr><td>-1</td><td>3</td><td>-2</td></tr></table>

<table><tr><td>4</td><td>-4</td><td>0</td></tr><tr><td>-1</td><td>3</td><td>-2</td></tr><tr><td>-3</td><td>1</td><td>2</td></tr></table>

The other cases (where the position of 4-4 is different) can be obtained by rotating one of the above configurations. Hence all 3232 ways of filling in the table in which all row and column sums are zero will also have both diagonal sums being nonnegative. It follows that the answer is 3232.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.