Kvant Math Problem 1123

Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m09s
Source on kvant.digital

Problem

A right angle is partitioned into infinitely many unit square cells. Consider the rows of cells parallel to the sides of the angle (“vertical” and “horizontal” rows). Is it possible to write a positive integer in each cell so that every vertical row and every horizontal row contains each positive integer exactly once?

V. S. Shevelev

Tournament of Towns (Spring 1988)

Exploration

Label the cells by coordinates $(i,j)$, where $i,j\in\mathbb N$ and $i,j\ge 1$. The cell $(i,j)$ lies in the $i$-th vertical row and the $j$-th horizontal row. The requirement is that every row and every column contain each positive integer exactly once.

Thus we are asking whether there exists an infinite array $(a_{ij})$ of positive integers such that for every fixed $i$, the sequence $(a_{ij}){j\ge1}$ is a permutation of $\mathbb N$, and for every fixed $j$, the sequence $(a{ij})_{i\ge1}$ is also a permutation of $\mathbb N$.

This is an existence problem. A first attempt is the addition table $a_{ij}=i+j$, but then the number $1$ never appears. The multiplication table also fails because rows are not permutations.

A natural candidate is obtained by looking at binary expansions. Write $i-1$ and $j-1$ in base $2$, and combine their digits by bitwise exclusive OR. Define

$$a_{ij}=((i-1)\oplus(j-1))+1.$$

For a fixed $i$, the map $x\mapsto x\oplus(i-1)$ is a bijection of the nonnegative integers, so the row is a permutation of $\mathbb N$. The same holds for columns.

The only point requiring care is that the problem is phrased geometrically. After introducing coordinates, the geometric condition becomes exactly the existence of such an infinite Latin square on the positive integers. The XOR construction appears to satisfy everything.

The step most likely to hide an error is proving rigorously that $x\mapsto x\oplus c$ is a bijection of the nonnegative integers. The reason is that one must verify both injectivity and surjectivity, not merely appeal to intuition about binary digits.

Problem Understanding

The cells of the quarter-plane are arranged in infinitely many vertical and horizontal rows. We must place a positive integer in every cell so that in every vertical row each positive integer occurs exactly once, and in every horizontal row each positive integer occurs exactly once.

This is a Type D problem, an existence problem.

The task is to construct an infinite array whose rows and columns are all permutations of the positive integers. The core difficulty is finding a rule that simultaneously makes every row and every column contain every positive integer exactly once.

The answer is yes. A suitable construction comes from binary arithmetic: if the cell $(i,j)$ receives the number $((i-1)\oplus(j-1))+1$, where $\oplus$ denotes bitwise exclusive OR, then every row and every column becomes a permutation of the positive integers.

Proof Architecture

Lemma 1. For every nonnegative integer $c$, the map $T_c(x)=x\oplus c$ is a bijection of the set of nonnegative integers; this holds because $T_c(T_c(x))=x$ for every $x$.

Lemma 2. For every fixed $i$, the sequence $a_{ij}=((i-1)\oplus(j-1))+1$ contains every positive integer exactly once; this follows from Lemma 1 applied to $c=i-1$.

Lemma 3. For every fixed $j$, the sequence $a_{ij}=((i-1)\oplus(j-1))+1$ contains every positive integer exactly once; this follows from Lemma 1 applied to $c=j-1$.

The hardest point is Lemma 1, since the entire construction depends on the bijectivity of XOR with a fixed integer.

Solution

Number the vertical rows and horizontal rows by the positive integers. Let $(i,j)$ denote the cell in the $i$-th vertical row and the $j$-th horizontal row.

For each cell define

$$a_{ij}=((i-1)\oplus(j-1))+1,$$

where $\oplus$ denotes bitwise exclusive OR of binary expansions.

We shall prove that this assignment satisfies the required condition.

Consider a fixed nonnegative integer $c$. Define

$$T_c(x)=x\oplus c.$$

Since XOR is performed independently on each binary digit, applying the same operation twice restores every digit. Hence

$$T_c(T_c(x)) =(x\oplus c)\oplus c =x$$

for every nonnegative integer $x$.

Thus $T_c$ is its own inverse. Consequently $T_c$ is a bijection of the set of nonnegative integers.

Now fix a vertical row $i$. As $j$ runs through the positive integers, the number $j-1$ runs through all nonnegative integers. The entries in row $i$ are

$$((i-1)\oplus(j-1))+1.$$

By the bijectivity of $T_{,i-1}$, the values

$$(i-1)\oplus(j-1)$$

run through all nonnegative integers exactly once. After adding $1$, the entries of row $i$ run through all positive integers exactly once.

The same argument applies to a fixed horizontal row $j$. As $i$ runs through the positive integers, the values

$$(i-1)\oplus(j-1)$$

run through all nonnegative integers exactly once because $T_{,j-1}$ is a bijection. Therefore the entries of column $j$ run through all positive integers exactly once.

Every vertical row and every horizontal row therefore contains each positive integer exactly once.

The required arrangement exists. One such arrangement is

$$a_{ij}=((i-1)\oplus(j-1))+1.$$

$$\boxed{a_{ij}=((i-1)\oplus(j-1))+1}$$

Verification of Key Steps

The first delicate step is the claim that XOR with a fixed integer is bijective. A careless argument might assert that binary digits are merely “rearranged”, which is false. The correct reason is stronger: for every $x$,

$$(x\oplus c)\oplus c=x.$$

Hence the map is its own inverse. Injectivity and surjectivity follow simultaneously.

The second delicate step is verifying that a row contains every positive integer, not merely infinitely many distinct integers. Fix $i$. Given any positive integer $n$, let

$$j=((n-1)\oplus(i-1))+1.$$

Then

$$a_{ij} =((i-1)\oplus((n-1)\oplus(i-1)))+1 =n.$$

Thus every positive integer occurs in that row. Uniqueness follows from injectivity of the XOR map.

The third delicate step is the passage from nonnegative integers to positive integers. XOR naturally acts on ${0,1,2,\dots}$. The shift by $1$ converts this set bijectively into ${1,2,3,\dots}$, so no positive integer is omitted and none is repeated.

Alternative Approaches

The construction can be viewed group-theoretically. The set of all finite binary sequences forms the countable abelian group

$$\bigoplus_{k\ge0}\mathbb Z_2.$$

After numbering its elements by the positive integers, one may place in position $(i,j)$ the group sum of the elements corresponding to $i$ and $j$. Every row and every column is then a translate of the whole group, hence a permutation of its elements. Translating back to positive integers yields the required array.

The XOR description is preferable because it gives an explicit formula in ordinary arithmetic notation and makes the verification immediate through the identity $(x\oplus c)\oplus c=x$.