I'm trying to solve the combinatorics problems provided in Yufei Zhao's blog. Can you help me with this one?
China (1993):
A group of $10$ people went to a bookstore. It is known that
- Everyone bought exactly $3$ books;
- For every two persons, there is at least $1$ book that both of them bought.
What is the least number of people that could have bought the book purchased by the greatest number of people?
Ross's argument shows that to achieve four you'd have to have each book bought by exactly four people. That isn't possible, since there are exactly 30 purchases, and 30 isn't divisible by $4$.
Reproducing Ross's logic here, with my edits:
This leaves the question of $5$. You can achieve this by using the projective plane of order two, with the points as books, and having the first seven people buy books associated with distinct lines, and the last three buy books corresponding to three of the lines, not all colinear. This looks like:
$$\{a,b,c\}\\ \{a,b,c\}\\ \{c,d,e\}\\ \{c,d,e\}\\ \{e,f,a\}\\ \{e,f,a\}\\ \{a,g,d\}\\ \{c,g,f\}\\ \{e,g,b\}\\ \{b,d,f\}$$
Book $a,c,e$ are bought five times, $b,d,f$, four times, $g$ three times.
A counting argument to exclude $4$
Let $n_k$ be the number of books bought by $k$ people.
Then $$\sum_k kn_k =30\\\sum_{k}\binom{k}{2}n_k\geq 45$$
The first is just saying a total of $30$ books were purchased.
The second is saying that if we count all the pairs of people that bought each book, then we get at least $\binom{10}{2}=45$, because each pair of people is counted in at least one book.
But if the maximum is four - that is $n_k=0$ for $k>4$ - then these formula mean:
$$n_1+2n_2+3n_3+4n_4=30\\ n_2+3n_3 + 6n_4\geq 45$$
Multiplying by $3$ and $2$ and subtracting, we get:
$$-3n_3-4n_2-3n_1\geq 0$$
Which is only possible if $n_1=n_2=n_3=0$, but then there is no solution to $4n_4=30$.
Generalizations
More generally, if you have $p$ people and each buys exactly $b$ books, and each pair of people buys at least one book in common, then we get that the min-max $M$ must satisfy:
$$M\geq \frac{p-1}{b}+1$$
with equality eliminated except when $b\mid {p-1}$ and $\frac{(p-1)}b+1\mid bp$.
With $p=10,b=3$ you get that $m\geq\frac{9}{3}+1=4$ with equality eliminated because, while $b\mid p-1$, we have that $(p-1)/b+1=4\not\mid 30=bp$.
If each pair of people have to have $d$ books in common, then the minimum is:
$$M\geq \frac{d(p-1)}{b} +1$$
with equality excluded when that is not an integer or if it is but it does not divide $bp$.
(Just to be clear - I am not saying that I know it is possible when that is an integer etc., only that this argument does not exclude the possibility. You'd still need to find a way to have every book bought $M$ times.)
This lower bound is exactly the bound you would have gotten if you reproduced Ross's argument in this general:
Some checks of simple cases
When $d=b$, this result says would say the obvious - that all the books must be bought by all $p$ people.
Similarly, when $d=0$, this result gives a trivial result that no book needs to be bought more than once.
There is the obvious case of $(p,b,d)=(n^2+n+1,n+1,1)$ which arises from the projective plane. Then $M=n+1$ is achievable.
Is there a configuration with $(p,b,d)=(11,5,2)$? Then we have all the divisibility requirements, and we get a possible $M=5$. There is something called the "Paley biplane" which fits this bill.
There are only 18 known examples of biplanes, which would correspond to the $d=2$ minimal case, but the order $n$ biplane would correspond to $(p,b,d)=\left(1+\frac{(n+1)(n+2)}{2},n+2,2\right)$. Here, $d(p-1)/b+1=n+2$ is an integer, and $n+2=b\mid bp$ so this triple does not let us exclude the existence of biplanes, but only 18 biplanes are know, so it appears that it might be difficult or impossible to characterize when a configuration for the minimum exists for $(p,b,d)$.