Maths Olympiad Prep

Track / Stage 3 / 174 of 260 #174 of 1964

Problem 174

AMC 10/12, early questions
Combinatorics Difficulty 3.5 Multiple choice

The three row sums and the three column sums of the array
[492816357]\left[\begin{matrix}4 & 9 & 2\\ 8 & 1 & 6\\ 3 & 5 & 7\end{matrix}\right]
are the same. What is the least number of entries that must be altered to make all six sums different from one another?

Pick one

Official solution

If you change 33 numbers, then you either change one number in each column and row (ie sudoku-style):
[928635]\left[\begin{matrix}* & 9 & 2\\ 8 & * & 6\\ 3 & 5 & *\end{matrix}\right]
Or you leave at least one row and one column unchanged:
[926357]\left[\begin{matrix}* & 9 & 2\\ * & * & 6\\ 3 & 5 & 7\end{matrix}\right]
In the first case, you are changing just one common number in two sums, so you wind up with three pairs of sums. (In the example given, the sum in row xx is the same as in column xx.)
In the second case, since two of the sums are unchanged, and the sums started out equal, they must remain equal. (In the second example given, row 33 and column 33 are untouched.)
Either way, 33 changes is not enough. However, building on the second example, if you change either the untouched column or the untouched row, you will get a possible answer:
[92637]\left[\begin{matrix}* & 9 & 2\\ * & * & 6\\ 3 & * & 7\end{matrix}\right]
Letting the * be a zero does indeed give 66 different sums, so the answer is 44, which is option D\boxed{D}.

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