Geometric solution to classic committee problem

Question

Most people know the classic committe style problems.

I read this solution to one of the basic version of the committe problem and was impressed, but not sure why it works.

I was hoping someone could explain why does it work.

Answer 1

Short answer: plane geometry mod $2$.

A longer answer:

There are two different facts in play here.

One is that this type of combinatorial construction is called a block design and is in fact a more special type of design called a finite geometry. It is similar to, but more general than, the geometry of points and lines, and the terminology is borrowed from geometry. The people in the linked example are what in a design are called "blocks", in a finite geometry are called "lines", and the committees are called "points".

The other fact is that there are finite forms of $n$-dimensional coordinate geometry, and for $n=2$ these are the easiest way to construct very symmetrical and efficient finite geometries (and thus block designs). For example, take the $49$ points in the plane with integer coordinates modulo $7$, and all $56$ different lines that are solutions sets of $Ax + By + C = 0 \mod 7$ with $(A,B)$ integers that do not both reduce to $0 \mod 7$.

The same construction mod $2$ has $4$ points and $3 \times 2=6$ lines through each point, and a unique line through every two points. The picture in the link is a drawing of the Cartesian plane mod $2$.

The combinatorics is most perfect when using points and lines from the projective geometry over a finite field, because of the duality between points and lines. In the example mod $7$, the projective plane has $57$ points, $57$ lines, every two distinct lines intersect in one point, every two distinct points have a line that contains them, there are $8$ lines through every point, and $8$ points on every line, which treats points and lines symmetrically. In this problem, the $\mod 2$ design could have been extended to a projective one with $7$ points and lines, $3$ lines through every point and $3$ points on every line, and can be thought of as the projective plane with one line (and its points) removed.

Answer 2

"A person is on exactly two committees" = "An intersection point is in exactly two lines"

"A committee contains exactly three people" = "A line contains exactly three intersection points"

"No two committees have more than one person in common" = "No two lines cross in more than one place"

This sort of solution wouldn't work in the same way if you changed the first or last restriction.