C8. Determine the largest $N$ for which there exists a table $T$ of integers with $N$ rows and 100 columns that has the following properties:
(i) Every row contains the numbers $1,2, \ldots, 100$ in some order.
(ii) For any two distinct rows $r$ and $s$, there is a column $c$ such that $|T(r, c)-T(s, c)| \geqslant 2$. Here $T(r, c)$ means the number at the intersection of the row $r$ and the column $c$.
Answer: The largest such integer is $N=100!/ 2^{50}$.
Solution 1.
Non-existence of a larger table. Let us consider some fixed row in the table, and let us replace (for $k=1,2, \ldots, 50$ ) each of two numbers $2 k-1$ and $2 k$ respectively by the symbol $x_{k}$. The resulting pattern is an arrangement of 50 symbols $x_{1}, x_{2}, \ldots, x_{50}$, where every symbol occurs exactly twice. Note that there are $N=100!/ 2^{50}$ distinct patterns $P_{1}, \ldots, P_{N}$.

If two rows $r \not s$ in the table have the same pattern $P_{i}$, then $|T(r, c)-T(s, c)| \leqslant 1$ holds for all columns $c$. As this violates property (ii) in the problem statement, different rows have different patterns. Hence there are at most $N=100!/ 2^{50}$ rows.

Existence of a table with $N$ rows. We construct the table by translating every pattern $P_{i}$ into a corresponding row with the numbers $1,2, \ldots, 100$. We present a procedure that inductively replaces the symbols by numbers. The translation goes through steps $k=1,2, \ldots, 50$ in increasing order and at step $k$ replaces the two occurrences of symbol $x_{k}$ by $2 k-1$ and $2 k$.
- The left occurrence of $x_{1}$ is replaced by 1 , and its right occurrence is replaced by 2 .
- For $k \geqslant 2$, we already have the number $2 k-2$ somewhere in the row, and now we are looking for the places for $2 k-1$ and $2 k$. We make the three numbers $2 k-2,2 k-1,2 k$ show up (ordered from left to right) either in the order $2 k-2,2 k-1,2 k$, or as $2 k, 2 k-2,2 k-1$, or as $2 k-1,2 k, 2 k-2$. This is possible, since the number $2 k-2$ has been placed in the preceding step, and shows up before / between / after the two occurrences of the symbol $x_{k}$.
We claim that the $N$ rows that result from the $N$ patterns yield a table with the desired property (ii). Indeed, consider the $r$-th and the $s$-th row $(r \neq s)$, which by construction result from patterns $P_{r}$ and $P_{s}$. Call a symbol $x_{i}$ aligned, if it occurs in the same two columns in $P_{\mathrm{r}}$ and in $P_{8}$. Let $k$ be the largest index, for which symbol $x_{k}$ is not aligned. Note that $k \geqslant 2$. Consider the column $c^{\prime}$ with $T\left(r, c^{\prime}\right)=2 k$ and the column $c^{\prime \prime}$ with $T\left(s, c^{\prime \prime}\right)=2 k$. Then $T\left(r, c^{\prime \prime}\right) \leqslant 2 k$ and $T\left(s, c^{\prime}\right) \leqslant 2 k$, as all symbols $x_{i}$ with $i \geqslant k+1$ are aligned.
- If $T\left(r, c^{\prime \prime}\right) \leqslant 2 k-2$, then $\left|T\left(r, c^{\prime \prime}\right)-T\left(s, c^{\prime}\right)\right| \geqslant 2$ as desired.
- If $T\left(s, c^{\prime}\right) \leqslant 2 k-2$, then $\left|T\left(r, c^{\prime}\right)-T\left(s, c^{\prime}\right)\right| \geqslant 2$ as desired.
- If $T\left(r, c^{\prime \prime}\right)=2 k-1$ and $T\left(s, c^{\prime}\right)=2 k-1$, then the symbol $x_{k}$ is aligned; contradiction.
In the only remaining case we have $c^{\prime}=c^{\prime}$, so that $T\left(r, c^{\prime}\right)=T\left(s, c^{\prime}\right)=2 k$ holds. Now let us consider the columns $d^{\prime}$ and $d^{\prime \prime}$ with $T\left(r, d^{\prime}\right)=2 k-1$ and $T\left(s, d^{\prime \prime}\right)=2 k-1$. Then $d \neq d^{\prime \prime}$ (as the symbol $x_{k}$ is not aligned), and $T\left(r, d^{\prime \prime}\right) \leqslant 2 k-2$ and $T\left(s, d^{\prime}\right) \leqslant 2 k-2$ (as all symbols $x_{i}$ with $i \geqslant k+1$ are aligned).
- If $T\left(r, d^{N}\right) \leqslant 2 k-3$, then $\left|T\left(r, d^{N}\right)-T\left(s, d^{\prime \prime}\right)\right| \geqslant 2$ as desired.
- If $T\left(s, c^{\prime}\right) \leqslant 2 k-3$, then $\left|T\left(r, d^{\nu}\right)-T\left(s, d^{\nu}\right)\right| \geqslant 2$ as desired.
In the only remaining case we have $T\left(r, d^{\prime \prime}\right)=2 k-2$ and $T\left(s, d^{\prime}\right)=2 k-2$. Now the row $r$ has the numbers $2 k-2,2 k-1,2 k$ in the three columns $d^{\prime}, d^{d}, c^{\prime}$. As one of these triples violates the ordering property of $2 k-2,2 k-1,2 k$, we have the final contradiction.
Comment 1. We can identify rows of the table $T$ with permutations of $\mathcal{M}:=\{1, \ldots, 100\}$; also for every set $S \subset \mathcal{M}$ each row induces a subpermutation of $S$ obtained by ignoring all entries not from $S$.

The example from Solution 1 consists of all permutations for which all subpermutations of the 50 sets $\{1,2\},\{2,3,4\},\{4,5,6\}, \ldots,\{98,99,100\}$ are even.

Solution 2. We provide a bit different proof why the example from Solution 1 (see also Comment 1) works.
Lemma. Let $\pi_{1}$ and $\pi_{2}$ be two permutations of the set $\{1,2, \ldots, n\}$ such that $\left|\pi_{1}(i)-\pi_{2}(i)\right| \leqslant 1$ for every $i$. Then there exists a set of disjoint pairs $(i, i+1)$ such that $\pi_{2}$ is obtained from $\pi_{1}$ by swapping elements in each pair from the set.
Proof. We may assume that $\pi_{1}(i)=i$ for every $i$ and proceed by induction on $n$. The case $n=1$ is trivial. If $\pi_{2}(n)=n$, we simply apply the induction hypothesis. If $\pi_{2}(n)=n-1$, then $\pi_{2}(i)=n$ for some $i<n$. It is clear that $i=n-1$, and we can also use the induction hypothesis.

Now let $\pi_{1}$ and $\pi_{2}$ be two rows (which we identify with permutations of $\{1,2, \ldots, 100\}$ ) of the table constructed in Solution 1. Assume that $\left|\pi_{1}(i)-\pi_{2}(i)\right| \leqslant 1$ for any $i$. From the Lemma it follows that there exists a set $S \subset\{1, \ldots, 99\}$ such that any two numbers from $S$ differ by at least 2 and $\pi_{2}$ is obtained from $\pi_{1}$ by applying the permutations $(j, j+1)$, $j \in S$. Let $r=\min (S)$. If $r=2 k-1$ is odd, then $\pi_{1}$ and $\pi_{2}$ induce two subpermutations of $\{2 k-2,2 k-1,2 k\}$ (or of $\{1,2\}$ for $k=1$ ) of opposite parities. Thus $r=2 k$ is even. Since $\pi_{1}$ and $\pi_{2}$ induce subpermutations of the same (even) parity of $\{2 k, 2 k+1,2 k+2\}$, we must have $2 k+2 \in S$. Next, $2 k+4 \in S$ and so on, we get $98 \in S$, but then the parities of the subpermutations of $\{98,99,100\}$ in $\pi_{1}, \pi_{2}$ are opposite. A contradiction.

Comment 2. In Solution 2 we only used that for each set from $\{1,2\},\{2,3,4\},\{4,5,6\}, \ldots,\{98,99,100\}$ any two rows of $T$ induce a subpermutation of the same parity, not necessarily even.