USA Tstst

Proof. This can be achieved as follows: assuming the cells are labeled with $(x, y) \in \mathbb{Z}^2$, color a cell red if $x \equiv 0 \pmod{2^m}$ and $y \equiv 0 \pmod{2^{k-m}}$. For example, a $4 \times 2$ rectangle gets the following coloring:

A $2^m \times 2^{k-m}$ rectangle contains every possible pair $(x \pmod{2^m}, y \pmod{2^{k-m}})$ exactly once, so such a rectangle will contain one red cell (an odd number).

On the other hand, consider a $2^\ell \times 2^{k-\ell}$ rectangle with $\ell > m$. The set of cells this covers is $(x, y)$ where $x$ covers a range of size $2^\ell$ and $y$ covers a range of size $2^{k-\ell}$. The number of red cells is the count of $x$ with $x \equiv 0 \pmod{2^m}$ multiplied by the count of $y$ with $y \equiv 0 \pmod{2^{k-m}}$. The former number is exactly $2^{\ell-k}$ because $2^k$ divides $2^\ell$ (while the latter is 0 or 1) so the number of red cells is even. The $\ell < m$ case is similar. $\square$

Finally, given these $k+1$ colorings, we can add them up modulo 2, i.e. a cell will be colored red if it is red in an odd number of these $k+1$ colorings. We illustrate $n=4$ as an example; the coloring is 4-periodic in both axes so we only show one $4 \times 4$ cell.

This solves the problem.

Alternate proof of (ii) using generating functions

We will commit to constructing a coloring which is $n$-periodic in both directions. (This is actually forced, so it's natural to do so.) With that in mind, let
$$f(x, y) = \sum_{i=0}^{2^k-1} \sum_{j=0}^{2^k-1} \lambda_{i,j} x^i y^j$$
denote its generating function, where $f \in \mathbb{F}_2[x, y]$.

For this to be valid, we need that for any $2^p \times 2^q$ rectangle with area $n$, the sum of the coefficients of $f$ over it should be one, modulo $x^{2^k} = y^{2^k} = 1$. In other words, whenever $p+q=k$, we must have
$$f(x, y)(1 + \cdots + x^{2^p-1})(1 + \cdots + y^{2^q-1}) = (1 + \cdots + x^{2^k-1})(1 + \cdots + y^{2^k-1}),$$
taken modulo $x^{2^k} = y^{2^k} = 1$. The idea is to rewrite these expressions: because we're in characteristic 2, the given assertion is $(x+1)^{2^k} = (y+1)^{2^k} = 0$, and the requested property is
$$f(x, y)(x + 1)^{2^p - 1}(y + 1)^{2^q - 1} = (x + 1)^{2^k - 1}(y + 1)^{2^k - 1}.$$
Whenever $p+q=k$, we must have
$$g(x, y)x^{2^p-1}y^{2^q-1} = x^{2^k-1}y^{2^k-1},$$
$$g(x, y) = \sum_{p+q=k} x^{2^k-2^p} y^{2^k-2^q}$$
works. The end.