X marks the spot

Discrete Mathematics Level 4

Let \(G\) be a \(20 \times 20\) grid of squares. The rows of \(G\) have distinct labels taken from the set \(\{1,2, \ldots, 20\}\), and the columns of \(G\) have distinct labels taken from the set \(\{1,2,\ldots, 20\}\).

An \(X\) is placed in each position of the grid where the row and column have the same label. For each \(X\) in the grid, a line segment is drawn connecting it to any other \(X\) that is in an adjacent row or an adjacent column, or both.

Over all possible labeling of the rows and columns, what is the largest number of distinct lines segments that can be drawn by this process?

Details and assumptions

The row labels are distinct from each other, but not distinct from the column labels.

As an explicit example, if we have a \( 4 \times 4 \) grid and label the rows and columns as follows, we will place \(X\)'s as such:

\[ \begin{array} {c | c | c | c | c| } & 1 & 2 & 3 & 4 \\ \hline 3 & & & X & \\ \hline 1 & X & & & \\ \hline 2 & & X & & \\ \hline 4 & & & & X \\ \hline \end{array} \]

This will result in 5 line segments being drawn. Note that the \(X\) labelled with \( (1,1) \) and the \(X\) labelled with \((4,4) \) will not have a line segment drawn between them, as they are neither in an adjacent row, nor in an adjacent column. All the other pairs of \(X\)'s will have a line segment drawn between them.


Problem Loading...

Note Loading...

Set Loading...