Kvant Math Problem 164

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m48s
Source on kvant.digital

Problem

The textual version of the problem statement is currently being prepared. The graphical version can be found in the published issue.

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 left and right is equal to the sum of the two other numbers in the adjacent squares above and below it. It is known what number is written in one square of the $n$-th row (the blue cross in Figure 1), and it is required to determine the number written directly above it in the $(n+2)$-th row (the red question mark in the figure). How many additional numbers in the bottom two rows (the blue dots in the figure) must be known in order to do this?

Figure 1

M. L. Gerver

Exploration

Let the white squares be indexed by coordinates. Since only white squares carry numbers, it is natural to place coordinates so that a white square has coordinates $(i,j)$ with $i+j$ even. The condition at a black square $(i,j)$ is

$$a_{i-1,j}+a_{i+1,j}=a_{i,j-1}+a_{i,j+1}.$$

Rearranging,

$$a_{i,j+1}=a_{i-1,j}+a_{i+1,j}-a_{i,j-1}.$$

Thus every row can be computed from the two preceding rows. This already suggests a linear recurrence in the vertical direction.

To understand what information propagates upward, consider the effect of a single nonzero entry in the bottom row. Let row numbers increase upward. If row $0$ contains a $1$ at position $0$ and all other data in rows $0$ and $1$ vanish, successive rows are

$$1;\quad 0;\quad 1,1;\quad 0,0;\quad 1,2,1;\quad 0,0,0;\ldots$$

The coefficients are Pascal coefficients. Hence the value at a point in row $n+2$ is a linear combination of values in the bottom two rows, with coefficients coming from binomial expansions.

Introduce the horizontal shift operator $T$, defined by

$$(Tf)(x)=f(x+1).$$

The recurrence becomes

$$R_{k+1}=(T+T^{-1})R_k-R_{k-1}.$$

If one seeks the value directly above a chosen square in row $n$, the question becomes: which linear functionals on the initial two rows determine the coefficient of the corresponding entry in row $n+2$?

A Fourier mode $R_k=\lambda^k z^x$ gives

$$\lambda+\lambda^{-1}=z+z^{-1}.$$

Hence

$$(\lambda-z)(\lambda-z^{-1})=0.$$

Therefore every solution is a superposition of two independent families propagating as powers of $z$ and $z^{-1}$. This factorization suggests that the whole space of solutions restricted to the first $n+2$ rows has dimension equal to the number of boundary values in the first two rows.

The crucial question is not how to compute the desired entry when everything in the bottom rows is known, but how many boundary values are necessary and sufficient when one value in row $n$ is already given. The hidden issue is linear algebra: how many degrees of freedom remain after fixing that row-$n$ value?

The target value and the given row-$n$ value are two linear functionals on the space of solutions. One expects that fixing the row-$n$ value removes one degree of freedom. Thus the number of additional data required should be one less than the number needed to determine the target from the bottom boundary alone. The task is to compute that number precisely.

Problem Understanding

Numbers are written on the white squares of the infinite upper half-plane chessboard. For every black square, the sum of the numbers in the horizontal neighboring white squares equals the sum of the numbers in the vertical neighboring white squares.

One number in the $n$-th row is known. We wish to determine the number directly above it in the $(n+2)$-th row. Additional numbers may be specified in the bottom two rows. The problem asks for the minimum number of such additional values that must be known in order to determine the desired number uniquely.

This is a Type C problem. We must determine the minimum amount of information needed and prove that fewer data cannot suffice.

The governing relation is linear and second order in the vertical direction. The core difficulty is to count the relevant degrees of freedom. The answer will be obtained by expressing both the known value in row $n$ and the sought value in row $n+2$ as linear combinations of finitely many values in the bottom two rows and then comparing the corresponding linear functionals.

Proof Architecture

The first lemma states that if $R_k$ denotes the sequence of values in the $k$-th row, then

$$R_{k+1}=(T+T^{-1})R_k-R_{k-1}.$$

This is a direct rewriting of the condition at black squares.

The second lemma states that for fixed $n$, the value at a chosen square of row $n$ depends only on $n+1$ values in the bottom row and $n$ values in the second row, hence on exactly $2n+1$ boundary variables.

This follows by repeatedly applying the recurrence and observing the light-cone of influence.

The third lemma states that, as a linear functional of these $2n+1$ boundary variables, the value in row $n+2$ directly above the chosen square is independent of the value in row $n$.

This is proved by computing the corresponding coefficient polynomials. Their degrees differ, so the functionals are linearly independent.

The fourth lemma states that after fixing the value in row $n$, the remaining solutions form an affine space of dimension $2n$.

This is immediate from the previous lemma.

The hardest point is the independence of the two functionals. If they were proportional, knowing the row-$n$ value alone would already determine the row-$(n+2)$ value.

Solution

Number the rows from the bottom upward by

$$0,1,2,\ldots$$

and let $R_k$ denote the sequence of values in row $k$. Let $T$ be the horizontal shift operator. The condition at every black square gives

$$R_{k+1}=(T+T^{-1})R_k-R_{k-1}. \tag{1}$$

Fix a square in row $n$, and let $A$ be its value. Let $B$ be the value in the square directly above it in row $n+2$.

From (1), every row is obtained linearly from the two preceding rows. Repeated application of (1) shows that $A$ depends only on the values lying in its backward light-cone. More precisely, $A$ depends on exactly

$$n+1$$

squares of row $0$ and

$$n$$

squares of row $1$.

Hence $A$ is a linear functional on a vector space of dimension

$$(n+1)+n=2n+1. \tag{2}$$

The same set of boundary variables determines $B$.

Let

$$U=(u_1,\ldots,u_{2n+1})$$

denote these boundary variables. Then

$$A=L_n(U),\qquad B=L_{n+2}(U),$$

for two linear functionals $L_n$ and $L_{n+2}$.

We show that $L_n$ and $L_{n+2}$ are linearly independent.

Consider boundary data with row $1$ identically zero and row $0$ represented by a single basis vector. Under recurrence (1), the coefficients appearing in row $m$ are those of

$$(T+T^{-1})^{m}$$

modulo lower-order terms. Consequently the coefficient pattern for $A$ is given by a polynomial of degree $n$, whereas the coefficient pattern for $B$ is given by a polynomial of degree $n+2$.

A nonzero multiple of $L_n$ cannot equal $L_{n+2}$, because their highest-degree terms are different. Therefore

$$L_n,;L_{n+2}$$

are linearly independent.

The space of admissible boundary data has dimension $2n+1$. Imposing the known value

$$L_n(U)=A$$

cuts this dimension down by one. Thus the family of all solutions compatible with the given value $A$ has dimension

$$2n. \tag{3}$$

Since $L_{n+2}$ is independent of $L_n$, the value $B=L_{n+2}(U)$ still varies on that $2n$-dimensional family. Therefore fewer than $2n$ additional independent boundary values cannot determine $B$ uniquely.

Now suppose $2n$ suitable values in the bottom two rows are also specified. Together with the known value $A$, we then have

$$2n+1$$

independent linear conditions on the $2n+1$ boundary variables. These determine all boundary variables uniquely. Once the boundary data are known, recurrence (1) determines every higher row uniquely, and hence determines $B$.

Thus $2n$ additional numbers are sufficient, and by (3) no smaller number can suffice.

The required minimum number of additional known values is

$$\boxed{2n}.$$

Equality is achieved by specifying any collection of $2n$ boundary values which, together with the given value in row $n$, forms a system of $2n+1$ independent linear conditions on the relevant boundary variables.

Verification of Key Steps

The first delicate point is the count of relevant boundary variables. Tracing dependencies backward from a square in row $n$, each step enlarges the horizontal range by one on each side. After $n$ steps, the influence reaches exactly $n+1$ squares in row $0$. After $n-1$ steps, it reaches exactly $n$ squares in row $1$. No other boundary values can affect the chosen square.

The second delicate point is the independence of the functionals $L_n$ and $L_{n+2}$. If they were proportional, fixing the value in row $n$ would automatically fix the value two rows higher. Taking boundary data concentrated at one bottom square produces coefficient patterns whose leading terms arise from paths of lengths $n$ and $n+2$ respectively. Their degrees differ, so proportionality is impossible.

The third delicate point is the lower-bound argument. After fixing the row-$n$ value, the admissible data form an affine space of dimension $2n$. A linear functional independent of the imposed constraint cannot be constant on that space. Hence at least $2n$ further independent conditions are necessary.

Alternative Approaches

A more algebraic proof uses generating functions. Let

$$F_k(z)=\sum_x a_{x,k}z^x.$$

The recurrence becomes

$$F_{k+1}(z)=(z+z^{-1})F_k(z)-F_{k-1}(z).$$

For each fixed $z$, the vertical recurrence factors as

$$(\lambda-z)(\lambda-z^{-1})=0.$$

Thus every solution is a superposition of two propagation modes. Counting coefficients contributing to a chosen site in row $n$ again yields a space of dimension $2n+1$, and the desired conclusion follows from the independence of the row-$n$ and row-$(n+2)$ evaluation functionals.

The direct recurrence approach is preferable because it makes the finite light-cone structure explicit and turns the problem into a transparent dimension count.