Matrix problem with inductive solution

Question

Yesterday I was at an interview and was given the following problem:

Consider a matrix A that has dimensions NxM. Every element of the matrix is the average of its adjacent (up to 8) elements. Given that the element at position A[1][1]=1, find the element at A[N][M].

It was easy to notice that in such a matrix, all elements should be equal. Thus the element A[N][M]=1. I proved it for a 2x2 matrix, by assigning x,y,z to the unknown elements, getting a system of 3 equations and solving it. The explanation to my answer A[N][M]=1 was that for any such NxM matrix you will get a system of n*m-1 equations with as many variables, which after solving will all be equal to the A[1][1] element.

The interviewer requested an inductive solution. I claimed that this cannot be proved by induction as the P(n)(m) does not necessarily depend on P(n-1)(m-1). He proved it in the following steps.

• Prove it for the 2x2 matrix. (which I did)

• Assume that [N-1]x[M-1] is a matrix of all ones

• Enlarge the [N-1]x[M-1] matrix by one row and one column and start filling the final NxM matrix in the following way: Consider all the bottom and right 2x2 sub-matrices that include 2 known elements 1 and 2 unknown elements. As we had proved that 2x2 matrix can only have all ones, then the unknown elements should also be ones. Fill the Nth row and Mth column square by square to get the final matrix consisting of all 1s.

I have doubts that this is a correct method of solving this problem. Could you share your opinions and tell me whether the inductive step is acceptable?

Answer 1

The interviewer's solution is wrong. In the $3\times 3$ case, you have nine equations. One of them is identical to the one in the $2\times 2$ case, but the three edge squares of the $2\times 2$ case have different equations than in the $3\times 3$ case. Hence you may not conclude that in particular the $2\times 2$ solution must apply here.

Answer 2

Assume that A[N - 1][M-1] is a matrix of all ones

This is not a correct formulation of the inductive assumption. The inductive assumption is that any $(N - 1)$ by $(M - 1)$ sized table must contain only $1$s under the constraints. But one of those constraints is that there is no $N^{th}$ row and no $M^{th}$ column.

If this were a valid inductive assumption, then due to symmetry, you could make the inductive assumptions that all $N-1$ by $M-1$ subtables are filled with $1$s and the result follows with no further logic.

---

A better argument for why they are all equal is simply argument by contradiction and infinite descent.

Assume for the sake of contradiction that there are 2 adjacent cells which contain different values, $a$ and $b$, with $a > b$.

Since $b$ is adjacent to a larger value, it must also be adjacent to a lesser value. Call it $c$.

Since $c$ is adjacent to a larger value, it must also be adjacent to a lesser value. Call it $d$.

Etc. Infinite descent in a finite matrix.