VN IMO Booklet

a. First, consider an empty rectangle board of size $2^k\times 2018$ and $2^k$ binary sequences of length $k$. We write those sequences to the left of the board so that each row consists of a sequence. Thus, the rest to the right of the board are $2018-k$ empty columns. It is obvious that each of the first $k$ columns of the board (counting from the left) has exactly $2^{k-1}$ $0$s and $2^{k-1}$ $1$s. This board satisfies the given condition. We will prove that it is minimal.



For an arbitrary binary sequence $s=a_1{a}_2\dots a_{2018}$, we consider its subsequence $s^{\prime }=a_1{a}_2\dots a_k$. It is clear that $s^{\prime }$ appears at the beginning of some row in the board, so if we continue writing $a_{k+1},a_{k+2},\dots ,a_{2018}$ into the empty cells on that row, we will get $s$. Furthermore, there is exactly one row that contains $s^{\prime }$, so if we omit that row, we cannot form $s$ from any other row. Therefore, the above board is minimal.

b. Suppose that each of the first $k$ columns of the board consists of both $0$ and $1$. We will prove the following important remark.

Remark. All the cells in the last $2018-k$ columns (in other words, $2018-k$ columns to the right) of the board are empty.

Proof. Consider an arbitrary binary sequence $s$ of length $k$ and suppose $A_s$ be the set of rows with the property: the first $k$ cells of each row (counting from the left) form $s$. We will prove that there exists an element in $A_s$ of which all last $2018-k$ cells are empty.

Consider the $(k+1)$-th cell of each row in $A_s$. It is clear that those cells belong to the $(k+1)$-th column of the board which do not simultaneously have $0$ and $1$.

If no cell of this column is empty, we can suppose that all numbers in the column are $0$s. Then the binary sequence of form $s$ concatenation to $1$ cannot be formed by any row, which contradicts the complete property of the board. Thus, there exists a subset $A^{\prime }$ of $A$ such that the $(k+1)$-th cell of each row in $A^{\prime }$ is empty.

We continue considering the $(k+2)$-th cell and we can similarly prove that there exists a subset $A_s^{\prime \prime }$ of $A_s^{\prime }$ such that the $(k+2)$-th cell of each row in $A_s^{\prime \prime }$ is empty. Following the same pattern to the last column, we will have a row of which all cells from the $(k+1)$-th position to the last position are empty.

Therefore, for any binary sequence $s$ of length $k$, we can always find a row of which $2018-k$ last cells are empty. Note that these rows are not necessarily distinct since a row can form many binary sequences. Let $A$ be the set of all such rows.

By the definition of $A$, it is clear that any binary sequence of length $2018$ can be formed by an element of $A$. It is also obvious that every row in the board belongs to $A$, otherwise we can omit that row and the board is still complete, which contradicts the minimal property of the board. Thus $A$ is also the set of all rows in the board, which implies the last $2018-k$ columns of the board are empty. The remark is proved.

Since the sub-board formed by the last $2018-k$ columns is totally empty, it can represent any binary sequence of length $2018-k$. Moreover, the original board is minimal which implies that the sub-board formed by the first $k$ columns is also minimal.

Erasing all $2018-k$ columns, the rest is a sub-board of size $m\times k$. We number the row from $1$ to $m$ (from top to bottom) and let $A_i$ ($i=1,2,\dots ,m$) be the set of all binary sequences of length $k$ that can be formed by the $i$-th row.

Since the original board is minimal with respect to binary sequences of length $2018$, it follows that the above $m\times k$ sub-board is also minimal with respect to the binary sequences of length $k$. Set $B=A_1\cup A_2\cup \cdots \cup A_m$, it is clear that $|B|=2^k$ (since the sub-board can generate any binary sequence of length $k$).

For every $i$ ($i=1,2,\dots ,m$), there exists a binary sequence of length $k$ generated by the $i$-th row, otherwise we can omit the $i$-th row and the remaining rows can also generate all binary sequences of length $k$, which contradicts the minimal property of the sub-board. This means for every $i$, there exists a binary sequence $a_i$ such that $a_i\in A_i\subset B$ and $a_i\notin A_j$ for any $j\ne i$. This implies $|B|\ge m$.

Combining all above arguments, we have $m\le 2^k$, which is our desired conclusion. ■