Question 161
Consider a positive integer $m$ and a rectangle board of size $m \times 2018$ which consists of $m$ rows and $2018$ columns. We write $0$ or $1$ into some cells of the board (only one number in a cell) and the rest are left empty. The board is *complete* if for an arbitrary binary sequence $S$ of length $2018$, we can always choose a row of the board to write some more $0$s, $1$s so that $2018$ numbers on that row (without any change in order) form the sequence $S$ (in case the board already had a row which is $S$, it is also complete). The board is *minimal* if it is complete and if we omit any row in the board, it is no longer complete.
a. If $0 \le k \le 2018$, prove that there exists a minimal $2^k \times 2018$ board such that there are exactly $k$ columns, each of which consists of both $0$ and $1$ (there are possibly some empty cells on those columns).
b. A minimal $m \times 2018$ board which has exactly $k$ columns, each of which consists of both $0$ and $1$, is given. Prove that $m \le 2^k$.
a. If $0 \le k \le 2018$, prove that there exists a minimal $2^k \times 2018$ board such that there are exactly $k$ columns, each of which consists of both $0$ and $1$ (there are possibly some empty cells on those columns).
b. A minimal $m \times 2018$ board which has exactly $k$ columns, each of which consists of both $0$ and $1$, is given. Prove that $m \le 2^k$.