Suppose $n$ is a positive integer. Let ${\cal C}$ be a set of subsets of $X:=\{1,\ldots,n\}$ with the following properties:

  1. all members of ${\cal C}$ contain at least $2$ elements, and $X\notin {\cal C}$;
  2. $A\neq B\in {\cal C}$ implies $|A\cap B| = 1$; and
  3. $|{\cal C}| = n$.

Doe this imply that at least one of the following statements is true?

(S1) All members of ${\cal C}$ have equal cardinality (in that case ${\cal C}$ is called a "projective plane");

(S2) There is $A\in{\cal C}$ such that $|A| = n-1$ (in that case ${\cal C}$ is called a "near pencil").


Yes, it is true and known. See Bourbaki Theory of sets, excersises to the chapter III (ordered sets), $\S 5$ (properties of integers). It is ex. 14 in English edition of 1968.

The proof goes as follows. At first, we denote $|\cal C|=m$ and do not assume for a moment that $m=n$, but prove that $m\leqslant n$. Assume that some element $y$ belongs to a unique set $A\in \cal C$. If $|A|=2$, all sets in $\cal C$ should contain $A\setminus \{y\}$ and have no other common elements, this gives even $m\leqslant n-1$. If $|A|\geqslant 3$, we may remove $y$ from $X$ and from $A$ and (say, using induction) we again get $m\leqslant n-1$. So, we may suppose that each element $y$ belongs to at least two sets from $\cal C$.

Take an element $x\in X$ and a set $A\in \cal C$, denote $f(x)$ the number of sets containing $x$. Note that if $x\notin A$, then $f(x)\leqslant |A|$, else by pigeonhole principle there exist two sets $A_1,A_2\in \cal C$ containing $x$ for which $C_1\cap A=C_2\cap A$, and hence $|C_1\cap C_2|\geqslant 2$, a contradiction. Choose a set $A$ such that $|A|:=t$ is minimal. For any $a\in A$ choose a set $B_a\in \cal C$ containing $a$ and different from $A$. If $A=\{1,2,\dots,t\}$, we have $i\notin B_{i+1}$ (indicies are taken modulo $t$). Therefore $\sum_{i=1}^t f(i)\leqslant \sum_{i=1}^t |B_i|$. If now $X=\{1,\dots,n\}$, we have $f(i)\leqslant |A|$ for $i=t+1,\dots,n$. Summing up we get $\sum_{i\in X} f(i)\leqslant \sum_{i=1}^t |B_i|+(n-t)|A|$. But $\sum_{i\in X} f(i)=\sum_{B\in \cal C} |B|$, so we get that the sum of sizes of certain $m-t$ sets from $\cal C$ does not exceed $(n-t)|A|$. By minimality of $|A|$ this is not possible when $m>n$. If $m=n$, it is possible only if all sets except $B_1,\dots,B_t$ have size equal to $t$ and each element outside $A$ is contained exactly in $t$ sets from $\cal C$. Consider two cases.

1) $t=2$, $A=\{1,2\}$. If $1$ is contained in $f(1)=k+1$ sets from $\cal C$, then 2 is contained in $n-k$ sets from $\cal C$, and for all pairs of sets $B\ni 1$, $C\ni 2$ from $\cal C\setminus \{A\}$ the intersections $B\cap C$ are different, thus $n\geqslant 2+k(n-1-k)$, $k=1$ or $k=n-2$. If, say, $k=1$, then the set containing 1 different from $A$ contains $n-1$ elements and we get a near-pencil.

2) $t>2$. Since we have equality, we get $f(1)=|B_2|\geqslant t\geqslant 3$, so we may replace $B_1$ to a different set containing 1. This gives $|B_1|=t$. Analogously, all sets have cardinality $t$.

| cite | improve this answer | |
  • $\begingroup$ I don't have access to it. Can you give the solution? Thanks! $\endgroup$ – Dominic van der Zypen Apr 6 '17 at 7:59
  • $\begingroup$ Does this help : i.gyazo.com/b9544b5f0fd8ef47a7b2764bec168dbd.png ? $\endgroup$ – Philippe Gaucher Apr 6 '17 at 8:51
  • $\begingroup$ It contains only hints. I should probably write it down explicitly. $\endgroup$ – Fedor Petrov Apr 6 '17 at 9:12
  • $\begingroup$ @FedorPetrov You should add the picture to your answer to prevent it from expiring. $\endgroup$ – Philippe Gaucher Apr 6 '17 at 9:22
  • $\begingroup$ Thanks @FedorPetrov and Philippe! Yeah, if you could add the picture to the answer, that would be great $\endgroup$ – Dominic van der Zypen Apr 6 '17 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.