this problem follows from problem 2 of IMO 98. http://www.mathlinks.ro/Forum/resources.php?c=1&cid=16&year=1998&p=124458

Yes, it does mostly, but we need some extra things like an example: First, to show that $k \leq 2^n$, note that the conditions require each pair of columns to have at least $2^n$ disagreements. This is at least $k(k-1)2^{n-1}$ disagreements in total. If we look at rows instead of columns, a row with $a$ white squares and $b$ black squares has $ab$ disagreements, where $a+b=k$. So there are exactly $\sum ab$ disagreements; then $k(k-1)2^{n-1} \leq \sum ab$. But $ab \leq (a+b)^2/4=k^2/4$, so $k(k-1)2^{n-1} \leq 2(2^n-1)k^2/4$. Rearranging, $k \leq 2^n$. We make the example by induction. We will make it with $2^n-1$ rows instead of $2(2^n-1)$ and $2^{n-1}$ disagreements instead of $2^n$ (because then it suffices to duplicate the rows). For $n=1$, take one row of length $2^1$ with a $0$ and a $1$ (here we code black squares as $0$'s and white squares as $1$'s). If we have an example for $n$, we construct the one for $n+1$ as follows: take the top row and write $0$s in the first $2^n$ squares, then $1$s in the other $2^n$. We are left with a $2^{n+1}-2 \times 2^{n+1}$ board. Divide it into four $2^n-1 \times 2^n$ rectangles. Fill in the two rectangles under the $0$s, and one of the two under the $1$s, with the $n$-example; fill in the remaining rectangle with the $n$-example $+1 \pmod{2}$.