n = k2 - k + 1, where k is a prime plus one. Show that we can color some squares of an n x n board black so that each row and column has exactly k black squares, but there is no rectangle with sides parallel to the sides of the board which has its four corner squares black.
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 mod p, not all zero, and the coordinates are homogeneous, so that we regard (a, b, c), (2a, 2b, 2c), ... , ( (p-1)a, (p-1)b, (p-1)c ) as the same point. That gives (p3 - 1)/(p-1) = p2 + p + 1 points, which is the correct number.
We can take lines to be lx + my + nz = 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), ... , ( (p-1)l, (p-1)m, (p-1)n ) representing the same line.
One way of writing the points is p2 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 la + mb + 1.1 = 0, so there are p lines of the form (l, m, 1) which contain P. Similarly, there is a unique l such that la + 1b + 0.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 non-zero. 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).
Comment. This is a poor question. If you have not met finite projective geometries before, then you are in real difficulties. If you have, the proof is just tiresome verification.
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 2000