Problem 2089

a) Consider a table with $T+1$ rows and an infinite number of columns (towards right) such that the first column is filled by numbers $1, 2, \dots, T$ and $1$. An algorithm is introduced for filling the cells of the table, then $f_i(j)$ is defined as the value of the intersection cell of the $i^{th}$ row and the $j^{th}$ column of the table.

Label the cells of the table, except those of the first row, by $a_1, a_2, a_3, \dots$, like the following table.

In each step of the algorithm, some cells of the table are filled in a way that after the $j^{th}$ step $a_j$ is filled. Suppose that $a_j$ is at the intersection of the $k^{th}$ row and the $l^{th}$ column.

i. If $a_j$ was empty before the $j^{th}$ step, the smallest natural number that has not yet appeared in the table is written in $a_j$ at that step.

ii. The number in $a_j$ should be equal to the number of repetitions of $l$ in the $(k-1)^{th}$ row of the table $(*)$. For this reason, enough $l$'s should be put in the first empty cells of the $(k-1)^{th}$ row so that the number of $l$'s becomes equal to the number written in $a_j$. Using this algorithm, if $l > T$, before this step no $l$ exists in the $(k-1)^{th}$ row; and if $l \le T$, at most one such $l$ exists (the one in the first column). The reason is that every number that has been written in the $(k-1)^{th}$ row before this step, except the first number, is written when the algorithm was used for the first $l-1$ cells of the row, and in those steps only numbers less than $l$ were written. Since the number in $a_j$ is positive, it was not less than the number of $l$'s in the $(k-1)^{th}$ row (before this step), so a sufficient number of $l$'s (maybe zero) can always be added to satisfy $(*)$.

iii. If $a_j$ is in the second row, after the previous step the numbers in the first row should be copied into the cells of the last row.

Using this algorithm, all of the cells of the table are filled with natural numbers, and if $f_i(j)$ is defined to be the number in the $j^{th}$ cell of the $i^{th}$ row, $f_i$'s satisfy all of the problem's conditions.

b) Yes! To construct such functions an approach similar to the previous part is used, utilizing a table which is infinite from right and below. Like part (a), $j$ is written in the $j^{th}$ cell of the first column and the cells of the table, except those of the first row, are labeled by $a_1, a_2, \dots$ like the following table.

The table can be filled using the algorithm of part (a) (since no bottom row exists in this table, part iii of the algorithm is not necessary). Like before, it can be showed that $a_j$ is filled at the $j^{th}$ step and if $a_j$ is the intersection of the $k^{th}$ row and the $l^{th}$ column, the number in $a_j$ is not less than the number of $l$'s in the $(k-1)^{th}$ row.

Again, if $f_i(j)$ is defined as the number in the intersection of the $i^{th}$ row and the $j^{th}$ column, $f_i$'s satisfy all of the problem's conditions; and since the numbers in the first column are all distinct, functions $f_i$ are mutually unequal.