1997 AMC 12 Problem 16

Question

The three row sums and the three column sums of the array

\begin{bmatrix} 4&9&2\\ 8&1&6\\ 3&5&7 \end{bmatrix}

are the same. What is the least number of entries that must be altered to make all six sums different from one another?

1

2

3

4

5

Answer: D

Concepts:arrays invariants construction

Difficulty rating: 1860

Small hint:

With only three altered entries, examine the rows and columns containing no alteration

Big hint:

For an upper bound, try changing four entries so that their row and column effects are all distinct

Solution:

With at most three alterations, either two of the six lines are unchanged, or some altered entry is the only alteration in both its row and its column. In the first case those two sums remain equal; in the second, that entry changes its row sum and column sum by the same amount, so those two sums remain equal. Four suffice: replace

4,

1,

2,

6

by

5,

3,

7,

9,

respectively. The resulting row sums are

21,

20,

15

and column sums are

16,

17,

23.

Hence the minimum is

4,

and D is correct.