Problem A. 865. (November 2023)

A. 865. A crossword is a grid of black and white cells such that every white cell belongs to some \(\displaystyle 2 \times 2\) square of white cells. A word in the crossword is a contiguous sequence of two or more white cells in the same row or column, delimited on each side by either a black cell or the boundary of the grid.

Show that the total number of words in an \(\displaystyle n\times n\) crossword cannot exceed \(\displaystyle \frac{{(n+1)}^2}{2}\).

Proposed by Nikolai Beluhov, Bulgaria

(7 pont)

Deadline expired on December 11, 2023.

We adjoin one additional row of black cells at the bottom and one additional column of black cells on the right. From now on, we will be working with the resulting grid of size \(\displaystyle (n + 1) \times (n + 1)\).

Our strategy will be to assign two grid cells to each word in the crossword. However, this idea will not work in its simplest form, and there will be some complications that we will need to take care of.

Introduce a coordinate system such that the lower left corner cell is at \(\displaystyle (0, 0)\) and the upper right corner cell is at \(\displaystyle (n, n)\). If \(\displaystyle c\) is the cell at \(\displaystyle (x, y)\), then we write \(\displaystyle c + (u, v)\) for the cell at \(\displaystyle (x + u, y + v)\).

For every horizontal word in the crossword, draw an arrow pointing from its rightmost white cell to the black cell immediately on the right. Similarly, for every vertical word in the crossword, draw an arrow pointing from the black cell that marks the word's lower end to the white cell immediately on top. (These black cells are guaranteed to exist because of the row and column we adjoined in the beginning.)

These arrows form several oriented paths, each one advancing up and to the right.

We say that a path is special when it is of the form \(\displaystyle c_1c_2c_3\) with \(\displaystyle c_1\) white, \(\displaystyle c_2\) black, \(\displaystyle c_3\) white, and \(\displaystyle c_2 + (-1, 1)\) black. We will deal with all nonspecial paths first, and we will consider the special paths separately after that.

Consider, then, an arbitrary nonspecial path \(\displaystyle P = c_1 c_2 \ldots c_{k + 1}\) with \(\displaystyle k\) arrows. We are going to assign \(\displaystyle 2k\) grid cells to \(\displaystyle P\), two for each word whose arrow belongs to \(\displaystyle P\). We do this as follows. All cells traversed by \(\displaystyle P\) are assigned to \(\displaystyle P\). Additionally, for all \(\displaystyle 2 \le i \le k\), cell \(\displaystyle a_i + (-1, 1)\) is assigned to \(\displaystyle P\). Since every white cell belongs to some \(\displaystyle 2 \times 2\) square of white cells, and since \(\displaystyle P\) is not special, these \(\displaystyle k - 1\) cells are guaranteed to exist, to be white, and to not be traversed by any of our paths. Thus, in particular, all cells assigned to \(\displaystyle P\) will be either white or traversed by \(\displaystyle P\).

We proceed to take care of the special paths.

First off, to each special path we assign the three cells that it traverses.

By this point, a black cell \(\displaystyle c\) is assigned to a path if and only if at least one of \(\displaystyle c + (0, 1)\) and \(\displaystyle c + (-1, 0)\) is white. And a white cell \(\displaystyle c\) is assigned to a path if and only if one of the following has taken place: (i) At least one of \(\displaystyle c + (1, 0)\) and \(\displaystyle c + (0, -1)\) is black; (ii) Both of these cells are white whereas \(\displaystyle c + (1, -1)\) is black; or (iii) All three cells listed in (i) and (ii) are white whereas both of \(\displaystyle c + (2, -1)\) and \(\displaystyle c + (1, -2)\) are black.

Next up, we define a surplus diagonal as follows. (In the figure, W stands for a white cell, B for a black cell, - for a cell whose colour does not matter, and ? for a cell whose colour we do not know precisely but is important to the definition.)

\(\displaystyle \begin{matrix} - & ? & - & - & - & - & - & -\\ ? & W & W & - & - & - & - & -\\ - & W & W & B & - &- &- &-\\ -& -& B& W& W& -& -& -\\ -& -& -& W& W& B& -& -\\ -& -& -& -& B& W& W& -\\ -& -& -& -& -& W& W& B\\ -& -& -& -& -& -& B& B\\ \end{matrix}\)

Every surplus diagonal either begins on white, or it begins on black. If cells \(\displaystyle d\), \(\displaystyle d + (0, -1)\), \(\displaystyle d + (1, 0)\), and \(\displaystyle d + (1, -1)\) form a white \(\displaystyle 2 \times 2\) square and at least one of cells \(\displaystyle d + (0, 1)\) and \(\displaystyle d + (-1, 0)\) is either white or nonexistent, then this is the first white \(\displaystyle 2 \times 2\) square in a surplus diagonal that begins on white. On the other hand, if cells \(\displaystyle d\), \(\displaystyle d + (0, -1)\), and \(\displaystyle d + (1, 0)\) are all black, then cells \(\displaystyle d + (0, -1)\) and \(\displaystyle d + (1, 0)\) form the first black pair in a surplus diagonal that begins on black. For example, the surplus diagonal in the figure begins on white, assuming that at least one of the two cells marked ? is white.

Once a surplus diagonal starts, it advances down and to the right by alternating white \(\displaystyle 2 \times 2\) squares and diagonally adjacent black pairs. Say that \(\displaystyle \{d, d + (0, -1), d + (1, 0), d + (1, -1)\}\) is a white \(\displaystyle 2 \times 2\) square in a surplus diagonal \(\displaystyle D\). Then the black pair that follows it in \(\displaystyle D\) is \(\displaystyle \{d + (2, -1), d + (1, -2)\}\). Conversely, say that \(\displaystyle \{d + (0, -1), d + (1, 0)\}\) is a black pair in a surplus diagonal \(\displaystyle D\). Then the white \(\displaystyle 2 \times 2\) square that follows it in \(\displaystyle D\) is \(\displaystyle \{d + (1, -1), d + (1, -2), d + (2, -1), d + (2, -2)\}\). (This is shown in the figure.)

Eventually, every surplus diagonal either ends on white, or it ends on black. If \(\displaystyle \{d, d + (0, -1), d + (1, 0), d + (1, -1)\}\) is a white \(\displaystyle 2 \times 2\) square in a surplus diagonal \(\displaystyle D\) and at least one of cells \(\displaystyle d + (2, -1)\) and \(\displaystyle d + (1, -2)\) is white, then this is the last white \(\displaystyle 2 \times 2\) square in \(\displaystyle D\), and \(\displaystyle D\) ends on white. If \(\displaystyle \{d + (0, -1), d + (1, 0)\}\) is a black pair in a surplus diagonal \(\displaystyle D\) and cell \(\displaystyle d + (1, -1)\) is black, then this is the last black pair in \(\displaystyle D\), and \(\displaystyle D\) ends on black. For example, the surplus diagonal in the figure ends on black.

Note that every white \(\displaystyle 2 \times 2\) square belongs to a unique surplus diagonal, and every black pair of the form \(\displaystyle \{d + (0, -1), d + (1, 0)\}\) belongs to a unique surplus diagonal as well. This follows because of the condition that every white cell belongs to at least one \(\displaystyle 2 \times 2\) square of white cells.

Furthermore, note that if a surplus diagonal ends on white, then the top left white cell of its final white \(\displaystyle 2 \times 2\) square is unassigned, and if it ends on black, then the black cell sealing off its final black pair is unassigned. In this way, different surplus diagonals are associated with different unassigned cells.

We are going to show that the number of special paths does not exceed the number of surplus diagonals. Once we have done that, we can simply take as many unassigned cells as we need from the surplus diagonals and assign them to the special paths, completing the proof.

We proceed to assign to each special path some fractions of the beginnings and endings of certain surplus diagonals.

(Here, we use ``beginning'' and ``ending'' as abstract concepts. They do not refer to any specific cells or sets of cells in the surplus diagonal. So even a surplus diagonal which consists of a single white \(\displaystyle 2 \times 2\) square or a single diagonally adjacent black pair will still have a separate beginning and ending.)

Let \(\displaystyle P = c_1 c_2 c_3\) be a special path, with \(\displaystyle c_2 = (x, y)\). Then \(\displaystyle c_1 = (x - 1, y)\) is white, \(\displaystyle c_2\) is black, \(\displaystyle c_3 = (x, y + 1)\) is white, and \(\displaystyle d_2 = (x - 1, y + 1)\) is black.

Since every white cell belongs to some \(\displaystyle 2 \times 2\) square of white cells, \(\displaystyle c_1\) is the upper right cell of a white \(\displaystyle 2 \times 2\) square \(\displaystyle S_1\) and \(\displaystyle c_3\) is the lower left cell of a white \(\displaystyle 2 \times 2\) square \(\displaystyle S_3\), as shown in the figure.

\(\displaystyle \begin{matrix} -& -& W& W\\ -& B& W& W\\ W& W& B& -\\ W& W& -& -\\ \end{matrix}\)

Consider cells \(\displaystyle d_1 = d_2 + (-1, 0) = (x - 2, y + 1)\) and \(\displaystyle d_3 = d_2 + (0, 1) = (x - 1, y + 2)\).

Case 1. Both of those cells are black. Then some surplus diagonal ends at the black pair \(\displaystyle \{d_1, d_3\}\). Assign to \(\displaystyle P\) the ending of that surplus diagonal.

Case 2. Cell \(\displaystyle d_1\) is white and cell \(\displaystyle d_3\) is black. Consider the white \(\displaystyle 2 \times 2\) square \(\displaystyle K_1\) that cell \(\displaystyle d_1\) belongs to. (If there are two such squares, choose one arbitrarily.) Then some surplus diagonal ends at \(\displaystyle K_1\). Assign half of the ending of that surplus diagonal to \(\displaystyle P\). Furthermore, some surplus diagonal begins at the white \(\displaystyle 2 \times 2\) square \(\displaystyle S_1\). Assign half of the beginning of that surplus diagonal to \(\displaystyle P\).

Case 3. Cell \(\displaystyle d_1\) is black and cell \(\displaystyle d_3\) is white. This case is symmetric to Case 2.

Case 4. Both cells \(\displaystyle d_1\) and \(\displaystyle d_3\) are white. Consider the white \(\displaystyle 2 \times 2\) square \(\displaystyle K_1\) that cell \(\displaystyle d_1\) belongs to. (If there are two such squares, choose one arbitrarily.) Then some surplus diagonal ends at \(\displaystyle K_1\). Assign half of the ending of that surplus diagonal to \(\displaystyle P\). Similarly, consider the white \(\displaystyle 2 \times 2\) square \(\displaystyle K_3\) that cell \(\displaystyle d_3\) belongs to. (If there are two such squares, choose one arbitrarily.) Then some surplus diagonal ends at \(\displaystyle K_3\). Assign half of the ending of that surplus diagonal to \(\displaystyle P\), too.

Next up, consider cells \(\displaystyle e_1 = c_2 + (0, -1) = (x, y - 1)\) and \(\displaystyle e_3 = c_2 + (1, 0) = (x + 1, y)\).

Case 1. Both of those cells are black. Then some surplus diagonal begins at the black pair \(\displaystyle \{e_1, e_3\}\). Assign to \(\displaystyle P\) the beginning of that surplus diagonal.

Case 2. Cell \(\displaystyle e_1\) is white and cell \(\displaystyle e_3\) is black. Consider the white \(\displaystyle 2 \times 2\) square \(\displaystyle L_1\) that cell \(\displaystyle e_1\) belongs to. (If there are two such squares, choose one arbitrarily.) Then some surplus diagonal begins at \(\displaystyle L_1\). Assign half of the beginning of that surplus diagonal to \(\displaystyle P\). Furthermore, some surplus diagonal ends at the white \(\displaystyle 2 \times 2\) square \(\displaystyle S_1\). Assign half of the ending of that surplus diagonal to \(\displaystyle P\).

Case 3. Cell \(\displaystyle e_1\) is black and cell \(\displaystyle e_3\) is white. This case is symmetric to Case 2.

Case 4. Both cells \(\displaystyle e_1\) and \(\displaystyle e_3\) are white. Consider the white \(\displaystyle 2 \times 2\) square \(\displaystyle L_1\) that cell \(\displaystyle e_1\) belongs to. (If there are two such squares, choose one arbitrarily.) Then some surplus diagonal begins at \(\displaystyle L_1\). Assign half of the beginning of that surplus diagonal to \(\displaystyle P\). Similarly, consider the white \(\displaystyle 2 \times 2\) square \(\displaystyle L_3\) that cell \(\displaystyle e_3\) belongs to. (If there are two such squares, choose one arbitrarily.) Then some surplus diagonal begins at \(\displaystyle L_3\). Assign half of the beginning of that surplus diagonal to \(\displaystyle P\), too.

Observe that:

(a) To each special path, we have assigned some fractions of the beginnings and endings of certain surplus diagonals, with total weight two.

(b) From each white beginning of a surplus diagonal we have assigned half to at most two special paths, and similarly for white endings.

(This is not entirely obvious. Consider a surplus diagonal \(\displaystyle D\) which begins on the white \(\displaystyle 2 \times 2\) square \(\displaystyle \{d, d + (0, -1), d + (1, 0), d + (1, -1)\}\), and let \(\displaystyle M\) be the set of the middle cells of all special paths to which we have assigned half of the beginning of \(\displaystyle D\). Then our definitions ensure that at most one of the cells \(\displaystyle d + (0, 1)\), \(\displaystyle d + (1, 1)\), and \(\displaystyle d + (2, 0)\) is in \(\displaystyle M\); at most one of the cells \(\displaystyle d + (-1, 0)\), \(\displaystyle d + (-1, -1)\), and \(\displaystyle d + (0, -2)\) is in \(\displaystyle M\); and \(\displaystyle M\) does not contain any other cells. White endings behave similarly.)

(c) Each black beginning of a surplus diagonal we have assigned to at most one special path, and similarly for black endings.

(d) Each surplus diagonal possesses one beginning and one ending.

From (a), (b), (c), and (d), we derive that the number of special paths does not exceed the number of surplus diagonals, as needed. The solution is complete.

Remark. It is not too difficult to achieve \(\displaystyle n^2/2 - O(n)\) words, for instance by blackening all cells \(\displaystyle c = (x, y)\) such that \(\displaystyle c\) is sufficiently far away from the boundary of the grid and \(\displaystyle x + y\) is a multiple of four. Many other patterns of word density \(\displaystyle 1/2\) are possible as well.

Statistics:

8 students sent a solution.
7 points:	Szakács Ábel, Varga Boldizsár.
2 points:	1 student.
1 point:	2 students.
0 point:	3 students.

Problems in Mathematics of KöMaL, November 2023