X marks the spot

Probability Level 4

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

An XX is placed in each position of the grid where the row and column have the same label. For each XX in the grid, a line segment is drawn connecting it to any other XX 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×4 4 \times 4 grid and label the rows and columns as follows, we will place XX's as such:

12343X1X2X4X \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 XX labelled with (1,1) (1,1) and the XX labelled with (4,4)(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 XX's will have a line segment drawn between them.


Problem Loading...

Note Loading...

Set Loading...