X marks the spot

First of all, we show that configurations with labelled rows and columns as described in the problem are equivalent to configurations with one X in each row and each column. Clearly, there cannot be two X's in the same row/column, since each X has a unique row and a unique column. Also, every configuration with one X in each row and each column can have columns and edges labelled as described, since we can simply label the columns 1,2,3,... and for each column $i$ , take the row of the X and label it $i$ .

Secondly, we show that the number of line segments is at most $2n-2$ , where $n$ is the side-length. The number of pairs of X's in adjacent rows is equal to $n-1$ , and so is the number of X's in adjacent columns. If all of these line segments are distinct, then we get the desired maximum of $2n-2$ . If the line segments are distinct, there cannot be any pair of X's in adjacent rows and columns.

Finally, we present a construction for such a maximum. There is a construction for $n=4$ , as shown below (sorry, don't know how to make tables) $\ \ \ | X | \ \ \ | \ \ \ \\ \ \ \ | \ \ \ | \ \ \ | X \\ X | \ \ \ | \ \ \ | \ \ \ \\ \ \ \ | \ \ \ | X | \ \ \ \\$ If there is a construction for $n=k$ , then there is a construction for $n=k+1$ . If $k$ is even, then add a row to the right and a column to the bottom, and put an X in the bottom right corner. If $k$ is odd, then add a row to the right and a column to the top, and put an X in the top left corner. Clearly, X's placed in consecutive steps cannot be in the adjacent rows and columns, and also, the 5th X is not in adjacent rows and columns with any of the first 4. This construction shows that the maximum is achievable for any $n\ge 4$ , and so the answer is $2(20)-2=\boxed{38}$ .

The number of distinct lines that can be drawn by X's in adjacent columns is $n-1$ . Similarly, considering adjacent rows, there are $n-1$ more. Hence, by PIE, there are $(n-1)+(n-1)-a=2n-2-a$ total distinct, where $a$ is the number of cells that are adjacent both by column and by row. With the X's placed in $(1,1),(2,3),\dots,(10,19),(11,2),(12,4),\dots,(20,20)$ , $a=0$ giving the maximum, $2(20)-2=\boxed{38}$ .

The most important observation is that the only way the number of lines can be less than the maximum is when the X's are adjacent diagonally, since we get only one line instead of two possible.

Let's assume for a while that it's always possible to arrange the X's so that no two are diagonally adjacent. Then for each internal X (meaning that it does not lie neither in first nor last column nor row) we get $4$ lines. Accounting for the X's lying on the border, there are the following possibilities:

1. two lying in the corner -- we get $2\cdot 2 = 4$ lines in total,
2. one in the corner, two in middle of the side -- $2+ 2\cdot 3 = 8$ lines in total,
3. four in the middle of the side -- $4 \cdot 3 = 12$ lines in total.

Denoting the length of the grid by $n$ , we will get ${4n - 4 \over 2} = 2n - 2$ lines altogether (the $2$ in the denominator appears because each line belongs to two different X's). The answer thus is $2 \cdot 20 - 2 = \bf 38$ .

We need to prove that it's always possible to arrange X's non-diagonally (as per the initial discussion). Assuming $n \geq 6$ and $n$ even, simply label the columns as $(1, 2, 3, \dots, n)$ and the rows $(1, n/2+1, 2, n/2 + 2, \dots, n/2, n)$ .

This is all that is is needed to solve this problem with $n=20$ . Just for the sake of the completeness, note that similar arrangement works for $n$ odd for $n \geq 5$ . For $n = 4$ one can label the columns $(1, 2, 3, 4)$ and the rows $(3, 1, 4, 2)$ . For $n=3$ this no longer works and at least two of the X's are adjacent, so that $3$ is the maximum number of lines in this case.

The rules stipulate that we must place exactly one $X$ in each row and each column. This means that we are placing $n$ (which, here, is $20$ ) nonattacking rooks on an $n \times n$ chessboard. To maximize the number of segments, we want to minimize the number of repeats, and a repeat will only happen if two rooks are diagonally adjacent.

Fortunately, we can change the rooks into queens, since the $n\times n$ queens problem has a solution for all $n \geq 4$ (background knowledge, hehe). Thus, we can place $20$ nonattacking queens on our $20\times 20$ board, and so there will be a segment for each adjacent row and column. There are $19$ in each direction, leading to $\boxed{38}$ as our maximum number of segments.

(Incidentally, if we put the $X$ 's in a zigzag formation, such that the first one is at a1, the second at c2, the third at e3, ..., the eleventh at b11, the twelfth at d12, the thirteenth at f13, etc. then we have a solution to the $20\times 20$ queens problem. This method works for the $X$ 's here for arbitrary $n$ but it fails for certain values for the queens problem. If you're lost, you may want to look up algebraic notation.)