Browse · MathNet
PrintIrska
Ireland algebra
Problem
Suppose is an array of numbers, with , and denote by the number in the th row and th column. We say that is an averaging array if it has the following property: equals the average of the three numbers , , and , whenever . Let be the maximum of all values in the averaging array .
a. Prove that there exists such that either or equals .
b. There is a trivial way to get for any fixed choice of indices : just pick for all . For each fixed choice of indices either describe how to construct a non-trivial averaging array and for which equals the maximum value , or show that no such array exists.
a. Prove that there exists such that either or equals .
b. There is a trivial way to get for any fixed choice of indices : just pick for all . For each fixed choice of indices either describe how to construct a non-trivial averaging array and for which equals the maximum value , or show that no such array exists.
Solution
a. For part (i), first observe that if with , then the three neighbouring values that have average value must also equal , since otherwise at least one would have to be larger than . Then it is not hard to see that we can propagate this value to get that the subarray with main diagonal from position to must equal everywhere, thus yielding (i).
b. For (ii), it already follows from the previous paragraph that there are no non-trivial examples if . However, such non-trivial examples can be constructed in all other cases: just pick for all numbers in the subarray with main diagonal from to . This leaves some elements undefined (if ) or some elements undefined (if ). Put numbers strictly less than 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.
b. For (ii), it already follows from the previous paragraph that there are no non-trivial examples if . However, such non-trivial examples can be constructed in all other cases: just pick for all numbers in the subarray with main diagonal from to . This leaves some elements undefined (if ) or some elements undefined (if ). Put numbers strictly less than 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.
Techniques
Recurrence relationsInduction / smoothingAlgorithms