This was a competition problem?... First note that $k^2-k+1=\left(p+1\right)^2-\left(p+1\right)+1=p^2+p+1$, so our grid actually has $p^2+p+1$ rows and $p^2+p+1$ columns. Now we consider the projective plane $\mathbb{P}^2\left(\mathbb{Z}_p\right)$ over $\mathbb{Z}_p$ (the field of residues modulo $p$). This plane has $p^2+p+1$ points and $p^2+p+1$ lines. We can arbitrarily define a bijection between the $p^2+p+1$ rows of our grid and the $p^2+p+1$ points of the projective plane, and a bijection between the $p^2+p+1$ columns of our grid and the $p^2+p+1$ lines of the projective plane. Any square of the grid corresponds to a pair of a row and a column of the grid, and thus to a pair $\left(P;\;\ell\right)$ with $P$ being a point and $\ell$ a line in our projective plane. Let's write a "0" in that square if the point $P$ lies on the line $\ell$, and a "1" otherwise. Then, it is easily seen that the conditions of the problem are satisfied: - On each row, there are exactly $k = p + 1$ squares with "0"s, since each point in $\mathbb{P}^2\left(\mathbb{Z}_p\right)$ lies on exactly $p + 1$ different lines. - On each column, there are exactly $k = p + 1$ squares with "0"s, since each line in $\mathbb{P}^2\left(\mathbb{Z}_p\right)$ passes through exactly $p + 1$ different points. - There is no rectangle with sides parallel to the sides of the grid with "0"s on each of its four vertices; in fact, if such a rectangle would exist, then its two horizontal sides (rows) would correspond to two distinct points $P$ and $Q$, its two vertical sides (columns) would correspond to two distinct lines $\ell$ and $\ell^{\prime}$, and since all four vertices of the rectangle have "0"s written in them, we would have $P\in\ell$, $Q\in\ell$, $P\in\ell^{\prime}$, $Q\in\ell^{\prime}$, so the two distinct lines $\ell$ and $\ell^{\prime}$ would have two points $P$ and $Q$ in common, but this is impossible (two distinct lines intersect at one point only). Thus we have found the required positioning of "0"s and "1"s on the grid. Darij