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}$.
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 \( 2k-1 \) and \( 2k \) 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 \neq 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 \( 2k-1 \) and \( 2k \).

- 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 \( 2k-2 \) somewhere in the row, and now we are looking for the places for \( 2k-1 \) and \( 2k \). We make the three numbers \( 2k-2, 2k-1, 2k \) show up (ordered from left to right) either in the order \( 2k-2, 2k-1, 2k \), or as \( 2k, 2k-2, 2k-1 \), or as \( 2k-1, 2k, 2k-2 \). This is possible, since the number \( 2k-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_r \) and in \( P_s \). Let \( k \) be the largest index, for which symbol \( x_k \) is not aligned. Note that \( k \geqslant 2 \). Consider the column \( c' \) with \( T(r, c') = 2k \) and the column \( c'' \) with \( T(s, c'') = 2k \). Then \( T(r, c'') \leqslant 2k \) and \( T(s, c') \leqslant 2k \), as all symbols \( x_i \) with \( i \geqslant k+1 \) are aligned.

- If \( T(r, c'') \leqslant 2k-2 \), then \( |T(r, c'') - T(s, c'')| \geqslant 2 \) as desired.
- If \( T(s, c') \leqslant 2k-2 \), then \( |T(r, c') - T(s, c')| \geqslant 2 \) as desired.
- If \( T(r, c'') = 2k-1 \) and \( T(s, c') = 2k-1 \), then the symbol \( x_k \) is aligned; contradiction.

In the only remaining case we have \( c' = c'' \), so that \( T(r, c') = T(s, c') = 2k \) holds. Now let us consider the columns \( d' \) and \( d'' \) with \( T(r, d') = 2k-1 \) and \( T(s, d'') = 2k-1 \). Then \( d' \neq d'' \) (as the symbol \( x_k \) is not aligned), and \( T(r, d'') \leqslant 2k-2 \) and \( T(s, d') \leqslant 2k-2 \) (as all symbols \( x_i \) with \( i \geqslant k+1 \) are aligned).

- If \( T(r, d'') \leqslant 2k-3 \), then \( |T(r, d'') - T(s, d'')| \geqslant 2 \) as desired.
- If \( T(s, c') \leqslant 2k-3 \), then \( |T(r, d') - T(s, d')| \geqslant 2 \) as desired.

In the only remaining case we have \( T(r, d'') = 2k-2 \) and \( T(s, d') = 2k-2 \). Now the row \( r \) has the numbers \( 2k-2, 2k-1, 2k \) in the three columns \( d', d'', c' \). As one of these triples violates the ordering property of \( 2k-2, 2k-1, 2k \), 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.