VN-TST 2018 Problem 2

For every positive integer $m$ , a $m\times 2018$ rectangle consists of unit squares (called "cell") is called complete if the following conditions are met: i. In each cell is written either a " $0$ ", a " $1$ " or nothing; ii. For any binary string $S$ with length $2018$ , one may choose a row and complete the empty cells so that the numbers in that row, if read from left to right, produce $S$ (In particular, if a row is already full and it produces $S$ in the same manner then this condition ii. is satisfied). A complete rectangle is called minimal, if we remove any of its rows and then making it no longer complete.

a. Prove that for any positive integer $k\le 2018$ there exists a minimal $2^k\times 2018$ rectangle with exactly $k$ columns containing both $0$ and $1$ . b. A minimal $m\times 2018$ rectangle has exactly $k$ columns containing at least some $0$ or $1$ and the rest of columns are empty. Prove that $m\le 2^k$ .