Problem

Source: 2018 Vietnam Team Selection Test

Tags: combinatorics, rectangle



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$.