Problem 1836

Solution:

We can regard the rows as lines and the columns as points. Black squares denote incidence. So line 3 contains point 4 iff square $(3,4)$ is black. The condition about rectangles then means that there is at most one line through two distinct points.

Suppose we take the points to be $(a, b, c)$, where $a, b, c$ are residues $\bmod p$, not all zero, and the coordinates are homogeneous, so that we regard $(a, b, c)$, $(2a, 2b, 2c), \ldots, ((p-1)a, (p-1)b, (p-1)c)$ as the same point. That gives $\frac{p^3-1}{p-1} = p^2 + p + 1$ points, which is the correct number.

We can take lines to be $l x + m y + n z = 0$, where the point is $(x, y, z)$. In other words, the lines are also triples $(l, m, n)$, with $l, m, n$ residues mod $p$, not all zero and $(l, m, n), (2l, 2m, 2n), \ldots, ((p-1)l, (p-1)m, (p-1)n)$ representing the same line.

One way of writing the points is $p^2$ of the form $(a, b, 1)$, $p$ of the form $(a, 1, 0)$ and lastly $(1, 0, 0)$. Similarly for the lines. We must show that (1) each point is on $p+1$ lines (so each column has $p+1$ black squares), (2) each line has $p+1$ points (so each row has $p+1$ black squares), (3) two lines meet in just one point (so no rectangles).

(1): Consider the point $P(a, b, 1)$ with $a$ non-zero. Then for any $m$, there is a unique $l$ such that $l a + m b + 1 \cdot 1 = 0$, so there are $p$ lines of the form $(l, m, 1)$ which contain $P$. Similarly, there is a unique $l$ such that $l a + 1 b + 0 \cdot 1 = 0$, so one line of the form $(l, 1, 0)$ contains $P$. The line $(1, 0, 0)$ does not contain $P$. So $P$ lies on just $p+1$ lines. Similarly for $(a, b, 1)$ with $b$ nonzero. The point $(0, 0, 1)$ does not lie on any lines $(l, m, 1)$, but lies on $(l, 1, 0)$ and $(1, 0, 0)$, so again it lies on $p+1$ lines.

Consider the point $Q(a, 1, 0)$ with $a$ non-zero. For any $m$, there is a unique $l$ such that $Q$ lies on $(l, m, 0)$. There is also a unique $l$ such that $Q$ lies on $(l, 1, 0)$. $Q$ does not lie on $(1, 0, 0)$, so it lies on just $p+1$ lines. Similarly, the point $(0, 1, 0)$ lies on the $p$ lines $(l, 0, 0)$ and on $(1, 0, 0)$, but no others.

Finally, the point $(1, 0, 0)$ lies on the $p$ lines $(0, m, 1)$, the line $(0, 1, 0)$ and no others. Thus in all cases a point lies on just $p+1$ lines. The proof of (2) is identical.

(3). Suppose the lines are $(l, m, n)$ and $(L, M, N)$. If $l$ and $L$ are non-zero, then we can take the lines as $(1, m', n')$ and $(1, M', N')$. So any point $(x, y, z)$ on both satisfies $x + m' y + n' z = 0$ $(*)$ and $x + M' y + N' z = 0$. Subtracting, $(m' - M') y + (n' - N') z = 0$. The coefficients cannot both be zero, since the lines are distinct. So the ratio $y : z$ is fixed. Then $(*)$ gives the ratio $x : y$. So the point is uniquely determined. If just one of $l, L$ is non-zero, then we can take the lines as $(0, m', n')$, $(1, M', N')$. We cannot have both $m'$ and $n'$ zero, so the ratio $y : z$ is determined, then the other line determines the ratio $x : y$. So again the point is uniquely determined. Finally, suppose $l$ and $L$ are both zero. Then since the lines are distinct $y$ and $z$ must both be zero. So the unique point on both lines is $(1, 0, 0)$.