Problem A. 872. (February 2024)

A. 872. For every positive integer \(\displaystyle k\) let \(\displaystyle a_{k,1},a_{k,2},\ldots\) be a sequence of positive integers. For every positive integer \(\displaystyle k\) let sequence \(\displaystyle \{a_{k+1, i}\}\) be the difference sequence of \(\displaystyle \{a_{k, i}\}\), i.e. for all positive integers \(\displaystyle k\) and \(\displaystyle i\) the following holds: \(\displaystyle a_{k, i+1}-a_{k, i}=a_{k+1, i}\). Is it possible that every positive integer appears exactly once among numbers \(\displaystyle a_{k,i}\)?

Proposed by Dávid Matolcsi, Berkeley

(7 pont)

Deadline expired on March 11, 2024.

It is possible.

We construct the sequence by proceeding diagonally, meaning that in the \(\displaystyle n\)th step, we specify all values of \(\displaystyle a_{k,l}\) for which \(\displaystyle k+l=n+1\). In the first step, we specify the value of \(\displaystyle a_{1,1}\). Then, once we have completed the first \(\displaystyle (n-1)\) steps, i.e., we have determined all \(\displaystyle a_{k,l}\) for which \(\displaystyle k+l \leq n\), in the \(\displaystyle n\)th step, it suffices to specify the value of \(\displaystyle a_{n,1}\), which uniquely determines the diagonal: \(\displaystyle a_{n-1, 2}=a_{n,1}+a_{n-1,1}\), then \(\displaystyle a_{n-2,3}=a_{n-1,2}+a_{n-2,2}=a_{n,1}+a_{n-1,1}+a_{n-2,2}\), and so on, until we reach the end of the diagonal, which is \(\displaystyle a_{1,n}=a_{n,1}+a_{n-1,1}+a_{n-2,2}+\ldots +a_{1,n-1}\). So, summarizing, if we choose the \(\displaystyle a_{n,1}\) numbers, they uniquely determine all the numbers of the sequences, and it is clear that by defining the numbers this way, we will indeed obtain sequences such that the sequence \(\displaystyle \{a_{k+1,i}\}\) is the difference sequence of \(\displaystyle \{a_{k,i}\}\).

The idea is to simultaneously ensure that each cell contains a different positive integer and that every number appears somewhere in the sequence. Thus, we aim to insert the smallest positive integer into each cell such that it hasn't been used before, while ensuring that no repeated numbers occur. If we can achieve this, we obtain a suitable construction.

Let \(\displaystyle a_{1,1}=1\). Then, we alternately construct two auxiliary diagonals and one main diagonal. The purpose of the auxiliary diagonals is to fill them with large numbers, much larger than the sum of all previously determined numbers. After this, we state that by inserting the smallest previously not used integer \(\displaystyle x\) into the first element of the main diagonal, we obtain a diagonal that does not create repetitions.

When an auxiliary diagonal is constructed, we choose a number \(\displaystyle C\) for \(\displaystyle a_{n,1}\), which is more than \(\displaystyle 10\) times larger than the sum of all previously inserted numbers. Then the numbers in the auxiliary diagonal, \(\displaystyle C, C+a_{n-1,1}, C+a_{n-1,1}+a_{n-2,2}, \ldots , C+a_{n-1,1}+a_{n-2,2}+\ldots +a_{1,n-1}\) are all larger than any previously inserted number and obviously distinct from each other.

When a main diagonal follows, we have previously built two auxiliary diagonals. We denote the first element of the former as \(\displaystyle C\) and the first element of the latter as \(\displaystyle D\). Then, as we have written before, we insert \(\displaystyle x\) into the first cell of the main diagonal, which is the smallest positive integer not previously inserted into any diagonal. Now we just need to show that this determines the corresponding diagonal in such a way that no repeated numbers are included.

It is clear that \(\displaystyle C>10(x-1)\ge 5x\). The elements of the main diagonal increase monotonically due to the construction rule, so they are all distinct. The first element, \(\displaystyle x\), is distinct from all previous numbers by definition. The second element is \(\displaystyle D+x\). Since this is greater than \(\displaystyle D\), it cannot be equal to any previous element not in the latest diagonal, in which \(\displaystyle D\) and \(\displaystyle D+C\) are the first two numbers, and \(\displaystyle D<D+x<D+C\). The next element of the main diagonal is \(\displaystyle 2D+C+x\), and all other elements in this diagonal is bigger than this. We claim that even \(\displaystyle 2D+C+x\) is greater than any previously inserted number. This is because the largest previously inserted number is the last number of the preceding diagonal, obtained by adding the sum of all elements of the diagonal before it to \(\displaystyle D\). However, \(\displaystyle D\) is defined to be more than \(\displaystyle 10\) times larger than the sum of all previously inserted numbers, so the last element of the diagonal starting with \(\displaystyle D\) is less than \(\displaystyle 2D\), and thus less than \(\displaystyle 2D+C+x\).

With this, we have constructed suitable sequences, so we are done.

Statistics:

9 students sent a solution.
7 points:	Czanik Pál, Holló Martin, Nguyen Kim Dorka, Simon László Bence, Szakács Ábel, Varga Boldizsár, Wiener Anna.
3 points:	1 student.
1 point:	1 student.

Problems in Mathematics of KöMaL, February 2024