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_1a_2\dots a_{2018}$, we consider its subsequence $s' = a_1a_2\dots a_k$. It is clear that $s'$ 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'$, 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'$ of $A$ such that the $(k + 1)$-th cell of each row in $A'$ is empty.

We continue considering the $(k + 2)$-th cell and we can similarly prove that there exists a subset $A_s''$ of $A_s'$ such that the $(k + 2)$-th cell of each row in $A_s''$ 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 \dots \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 \neq i$. This implies $|B| \ge m$.

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