General Idea

(This is an example of a thought process by the writer.)

1. Fill all cells in row \(P_1\) and column \(Q_1\) with 0.
2. For the remaining cells, let \(S'_i\) be the string obtained by concatenating row \(i\) excluding column \(Q_1\), and \(T'_j\) be the string obtained by concatenating column \(j\) excluding row \(P_1\). Then, recursively write in the same way so that \(S'_{P_2} < S'_{P_3} < \dots < S'_{P_N}\) and \(T'_{Q_2} < T'_{Q_3} < \dots < T'_{Q_N}\) hold.

This seems to work.

→ Since equality is not allowed in lexicographical order, the condition “each remaining row and column must contain at least one 1” is added, making it difficult to recursively write in the same way…

→ It seems that it would work if we write 0 in row \(P_1\) and 1 in column \(Q_N\) to avoid having all cells filled with 0.

Solution

1. Write 0 in all cells of row \(P_1\).
2. Write 1 in all cells of column \(Q_N\) that are still empty.
3. For the remaining \((N-1) \times (N-1)\) cells, let \(S'_i\) be the string obtained by concatenating row \(i\) excluding column \(Q_N\), and \(T'_j\) be the string obtained by concatenating column \(j\) excluding row \(P_1\). Then, recursively write in the same way so that \(S'_{P_2} < S'_{P_3} < \dots < S'_{P_N}\) and \(T'_{Q_2} < T'_{Q_3} < \dots < T'_{Q_N}\) hold.

The grid filled by this algorithm will satisfy the conditions. In addition to the conditions stated in the problem, it also satisfies the condition:

• Each column contains at least one cell with 0.

This can be shown by induction on \(N\) from the following:

• Each column must contain at least one cell with 0 since 0 is always written in row \(P_1\).
• Row \(P_1\) does not contain 1, and row \(P_2\) contains 1, so \(S_{P_1} < S_{P_2}\) always holds.
• Column \(Q_N\) contains 1 except for row \(P_1\), and column \(Q_{N-1}\) contains cells with 0 written recursively except for row \(P_1\), so \(T_{Q_{N-1}} < T_{Q_N}\) always holds.
• The lexicographical order of \(S_{P_i}\ (2\leq i)\) is equal to the lexicographical order of \(S'_{P_i}\), so \(S_{P_2} < S_{P_3} < \dots < S_{P_N}\) is satisfied by recursive writing. The same applies to \(T_{Q_i}\ (i \leq N-1)\).

Also, considering the behavior of the recursive part, it turns out that the conditions can be satisfied by writing as follows in the order of \(i=1,2,\dots,N\):

• First, write 0 in the cells of row \(P_i\) that have not been written yet. Then, write 1 in the cells of column \(Q_{N+1-i}\) that are still empty.