I've been working on the following problem
For every issue in the Blue's association, a commission with 10 members (belonging the Blue's) is formed in order to solve the problem. The only condition is
There can't be two commissions having more than one member in common
The Blue's association has formed this year 40 commissions.
What's the minimal amount of members in the Blue's association?
I've only found out the following
For any commission you can form $\binom{10}{2}=45$ different pairs and none of them can appear in another commission.
Since 40 different commissions are formed, the minimal number of pairs is $45\times 40=1800$.
Denote by $n$ the number of members. Thus $$\binom{n}{2}≥1800\Rightarrow n>60$$
$$$$
The minimal amount of members has to be 100 or less.
You can observe a distribution for 100 members here
My question:
Is 100 the answer or is there an ever smaller possible amount of members?
If so, how can I prove it?
Best Answer
Let $i$ denote each member of Blue's association and assume that there are $N$ members in total, that is, $i=1,2,\cdots, N.$ And let $j,k=1,2,\ldots, 40$ denote each of 40 commission. We will show that $N$ is at least $82$.
Consider the set $$ S=\{(i,j,k)\;|\;1\leq i\leq N, 1\leq j<k\leq 40, i\text{ belongs to }j,k\text{-th commission.}\}. $$ Let $d_i$ denote the number of commissions that $i$ joined. We will calculate $|S|$ using double counting method. First, note that $$ |S|=\sum_{(i,j,k)\in S}1 = \sum_{1\leq j<k\leq 40} \sum_{i:(i,j,k)\in S}1\leq \sum_{1\leq j<k\leq 40}1=\binom{40}{2}, $$ since for each $j<k$, there is at most one $i$ in common. On the other hand, $$ |S| = \sum_{1\leq i\leq N} \sum_{(j,k):(i,j,k)\in S}1 = \sum_{1\leq i\leq N} \binom{d_i}{2}, $$ since for each $i$, the number of pairs $(j,k)$ that $i$ joined is $\binom{d_i}{2}$. We also have $$\sum_{1\leq i\leq N}d_i = 400,$$by the assumption.
Finally, note that the function $f(x)= \binom{x}{2} = \frac{x^2-x}{2}$ is convex. Thus by Jensen's inequality we have that $$ \binom{40}{2}\geq |S|=\sum_{1\leq i\leq N} \binom{d_i}{2}\geq Nf\left(\frac{\sum_i d_i}{N}\right)=N\binom{\frac{400}{N}}{2}. $$ This gives us the bound $$ 40\cdot 39 \geq 400\cdot(\frac{400}{N}-1), $$and hence $$ N \geq \frac{4000}{49} = 81.63\cdots $$ This establishes $N\geq 82$. However, I'm not sure if this bound is tight. I hope this will help.
$\textbf{Note:}$ If $N=82$ is tight, then above argument implies that $d_i$'s distribution is almost concentrated at $\overline{d} = 400/82 \sim 5$.
EDIT: @antkam's answer seemingly shows that $N=82$ is in fact optimal.