Competition problem — Algebra — Maths Olympiad Prep

Library / /34 of 39

Algebra Difficulty 6.0 AIME, harder Prove it Ireland

Suppose $A$ is an $n \times n$ array of numbers, with $n > 2$ , and denote by $A(i, j)$ the number in the $i$ th row and $j$ th column. We say that $A$ is an *averaging array* if it has the following property: $A(i, j)$ equals the average of the three numbers $A(i, j-1)$ , $A(i-1, j)$ , and $A(i-1, j-1)$ , whenever $i, j \in \{2, \dots, n\}$ . Let $M$ be the maximum of all values $A(i, j)$ in the averaging array $A$ .

a. Prove that there exists $i \in \{1, \dots, n\}$ such that either $A(i, 1)$ or $A(1, i)$ equals $M$ .

b. There is a trivial way to get $A(i_0, j_0) = M$ for any fixed choice of indices $i_0, j_0 \in \{1, \dots, n\}$ : just pick $A(i, j) = M$ for all $i, j$ . For each fixed choice of indices $i_0, j_0 \in \{1, \dots, n\}$ either describe how to construct a non-trivial averaging array and for which $A(i_0, j_0)$ equals the maximum value $M$ , or show that no such array exists.

Solution

a.
For part (i), first observe that if $A(i, j) = M$ with $i, j > 1$ , then the three neighbouring values that have average value $A(i, j)$ must also equal $M$ , since otherwise at least one would have to be larger than $M$ . Then it is not hard to see that we can propagate this value to get that the subarray with main diagonal from position $(1, 1)$ to $(i, j)$ must equal $M$ everywhere, thus yielding (i).

b.
For (ii), it already follows from the previous paragraph that there are no non-trivial examples if $i_0 = j_0 = n$ . However, such non-trivial examples can be constructed in all other cases: just pick $A(i, j) = M$ for all numbers in the subarray with main diagonal from $(1, 1)$ to $(i_0, j_0)$ . This leaves some elements $A(i, 1)$ undefined (if $i_0 < n$ ) or some elements $A(1, i)$ undefined (if $j_0 < n$ ). Put numbers strictly less than $M$ in all positions in the first row and first column that are not yet defined. Now fill in the rest of the array one row at a time from left to right, beginning with the first row and proceeding in the natural order. In all cases, the next position is uniquely defined in terms of the values we have already chosen. This is the required example.

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 and solution reproduced as published; topic and difficulty added by this site.