Belarusian Mathematical Olympiad

Answer: $k=n+1$. In total there are $2^{k-1}-1$ ways to split the rows into two groups and $2^n-1$ ways to select some set of columns. Since there is at least one column set for any row split and the column set uniquely defines the row split, $2^{k-1}-1\le 2^n-1$, and therefore $k\le n+1$. We will prove that for any $n$ there is a nice table $(n+1)\times n$.

Consider a table in which in the $i$-th row $1$'s are placed on the first $i-1$ positions and $0$'s are placed on the rest (in particular, in the first row are only zeros). Note that for any two consecutive rows $a_i$ and $a_i+1$, the parity of the number of $1$'s on the intersection with some set of columns of these two rows is the same if and only if there is no $i$-th column in this set. So, the presence or absence of $i$-th column in the set uniquely determines whether $a_i$ and $a_i+1$ belong to the same group or not.

Now for the given split of rows, select those and only those columns for which the row with the same number is in different group with the next row. The set of selected columns satisfies the condition, hence the table is nice.