Kvant Math Problem 164

Verified: yes
Verdicts: PASS + PASS
Solve time: 6m13s
Source on kvant.digital

Problem

On the white squares of an infinite chessboard filling the upper half-plane (Figure 1), some numbers are written so that for every black square, the sum of the numbers in the two adjacent squares to its right and left equals the sum of the two other numbers in the adjacent squares above and below it. The number in one square of the $n$-th row (the blue cross in Figure 1) is known, and it is required to determine the number in the $(n+2)$-th row directly above it (the red question mark in the figure). How many additional numbers in the two bottom rows (the blue dots in the figure) must be known for this?

Figure 1

M. L. Gerver

Exploration

Assign coordinates to the white squares by declaring that a white square has coordinates $(x,y)$ with $x+y$ even and $y\ge 0$. Let $a(x,y)$ denote the number written in that square.

For every black square, the condition of the problem becomes

$$a(x-1,y)+a(x+1,y)=a(x,y-1)+a(x,y+1).$$

Solving for the upper value gives

$$a(x,y+1)=a(x-1,y)+a(x+1,y)-a(x,y-1).$$

Hence every row is determined from the two rows immediately below it.

The quantity to be found is the number in the square directly above a given square. It is natural to compute the value two rows higher in terms of the two rows below. Using the recurrence twice,

$$\begin{aligned} a(x,y+2) &=a(x-1,y+1)+a(x+1,y+1)-a(x,y)\ &=\bigl(a(x-2,y)+a(x,y)-a(x-1,y-1)\bigr)\ &\qquad+\bigl(a(x,y)+a(x+2,y)-a(x+1,y-1)\bigr) -a(x,y), \end{aligned}$$

which simplifies to

$$a(x,y+2) = a(x-2,y)+a(x,y)+a(x+2,y) -a(x-1,y-1)-a(x+1,y-1).$$

For the target square,

$$a(0,n+2) = a(-2,n)+a(0,n)+a(2,n) -a(-1,n-1)-a(1,n-1).$$

The desired value is thus a linear combination of five entries in rows $n-1$ and $n$, one of which, namely $a(0,n)$, is already known.

Problem Understanding

A number in one square of the $n$-th row is given. Additional information may be supplied in rows $n-1$ and $n$. The task is to determine the minimum number of additional entries that guarantees determination of the number in the square directly above, two rows higher.

The formula obtained above immediately yields an upper bound of four. The essential issue is proving that no choice of only three additional entries can ever suffice.

Proof Architecture

The recurrence shows that arbitrary data on two consecutive rows determine a unique configuration in all higher rows.

The target value is a linear functional of the data in rows $n-1$ and $n$. Its explicit expression involves the four entries

$$a(-2,n),\quad a(2,n),\quad a(-1,n-1),\quad a(1,n-1),$$

together with the already known value $a(0,n)$.

Sufficiency follows from the explicit formula.

For necessity, the space of all admissible initial data in rows $n-1$ and $n$ is a vector space. After fixing the given value $a(0,n)$, the target depends on a nonzero linear functional of this space. It remains to show that its restriction to the subspace of configurations vanishing at every prescribed additional entry is still nonzero whenever at most three additional entries are fixed.

Solution

Let

$$V$$

be the vector space of all assignments of numbers to rows $n-1$ and $n$. Every element of $V$ extends uniquely to all higher rows by the recurrence

$$a(x,y+1)=a(x-1,y)+a(x+1,y)-a(x,y-1).$$

Fix the given value $a(0,n)$. Since the problem is linear, it suffices to study differences of configurations. Thus we may consider the subspace

$$W={,a\in V:\ a(0,n)=0,}.$$

The target value

$$T(a)=a(0,n+2)$$

is a linear functional on $W$. From the formula derived above,

$$T(a) = a(-2,n)+a(2,n)-a(-1,n-1)-a(1,n-1).$$

Suppose that, besides $a(0,n)$, at most three additional entries are known. Let these entries be located at positions

$$p_1,\dots,p_m, \qquad m\le 3,$$

in rows $n-1$ and $n$.

Consider the subspace

$$U={,a\in W:\ a(p_i)=0\text{ for }1\le i\le m,}.$$

If the prescribed data determined the target uniquely, then every element of $U$ would have to satisfy $T(a)=0$. In other words, the restriction of $T$ to $U$ would be the zero functional.

This is impossible. The functional $T$ involves only the four positions

$$(-2,n),\quad (2,n),\quad (-1,n-1),\quad (1,n-1).$$

Among these four positions, at most three can belong to the prescribed set ${p_1,\dots,p_m}$. Hence at least one of them, call it $q$, is not prescribed.

Define an element $a\in W$ by assigning value $1$ at $q$, value $0$ at every other position of rows $n-1$ and $n$, and then extending upward by the recurrence. This assignment lies in $U$, because all prescribed positions have value $0$.

Since $q$ is one of the four positions occurring in the formula for $T$, with coefficient either $1$ or $-1$,

$$T(a)=\pm1\neq0.$$

Thus the restriction of $T$ to $U$ is not zero.

Consequently, after fixing any three additional entries, there remain two admissible configurations agreeing on all known data but having different values of $a(0,n+2)$. Hence three additional numbers can never guarantee determination of the target.

For sufficiency, the identity

$$a(0,n+2) = a(-2,n)+a(0,n)+a(2,n) -a(-1,n-1)-a(1,n-1)$$

shows that knowing

$$a(-2,n),\qquad a(2,n),\qquad a(-1,n-1),\qquad a(1,n-1)$$

in addition to the given value $a(0,n)$ determines the required number immediately.

Therefore the minimum number of additional entries required is

$$\boxed{4}.$$

Verification of Key Steps

The recurrence imposes no compatibility conditions on two consecutive rows. Arbitrary values in rows $n-1$ and $n$ generate a unique configuration above them.

The computation of $a(x,y+2)$ is exact and yields the identity

$$a(x,y+2) = a(x-2,y)+a(x,y)+a(x+2,y) -a(x-1,y-1)-a(x+1,y-1).$$

The lower bound does not depend on choosing a particular set of four neighboring entries. For an arbitrary collection of at most three prescribed entries, at least one coefficient appearing in the target functional remains free. A configuration supported only at that position changes the target while leaving all prescribed values unchanged. This excludes every possible strategy using only three additional numbers.

Alternative Approaches

Introduce the shift operator $T$ along a row. The recurrence becomes

$$u_{y+1}=(T+T^{-1})u_y-u_{y-1}.$$

Applying it twice gives

$$u_{y+2} = (T^2+1+T^{-2})u_y -(T+T^{-1})u_{y-1}.$$

The coefficient of the central position reproduces

$$a(0,n+2) = a(-2,n)+a(0,n)+a(2,n) -a(-1,n-1)-a(1,n-1),$$

from which the same conclusion follows. The coordinate calculation above gives the result in a more elementary form.