Finding the minimal number of members

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.


This is just a partial answer. I will show that $85$ members suffice; I don't know if $85$ is the minimum.

Recall that a projective plane of order $n$ exists if $n$ is a prime power: it has $n^2+n+1$ points and $n^2+n+1$ lines; each line has $n+1$ points, and there are $n+1$ lines through each point; any pair of lines meets in a unique point, and any pair of points determines a unique line.

Consider a projective plane of order $9$; it has $9^2+9+1=91$ points and $91$ lines; there are $10$ points on each line and $10$ lines through each point. A set of points is in general position if no three of the points are collinear. Note that, if we have a set of $t$ points in general position, then the lines determined by those points (taken two at a time) cover a total of at most $t+8\binom t2$ points; as long as $t\le5$ then the number of covered points is at most $5+8\binom52=85\lt91$, so we can add another point to the set and still have them in general position. Thus we can find a set $S$ of $6$ points in general position.

Let the members of the Blue's association be the $91-6=85$ points which are not in $S$. The commissions are the lines which do not meet $S$; they have $10$ members each, and any two have exactly one member in common. Finally, by the in-and-out formula, the number of commissions is $$91-\binom61\cdot10+\binom62\cdot1=46.$$


P.S. Let $m$ be the minimum possible number of members. I showed above that $m\le85$. On the other hand, I have a small improvement on your lower bound $m\ge61$.

Suppose the $i^\text{th}$ member belongs to $d_i$ commissions; then $$\sum_{i=1}^md_i=400$$ since there are $40$ commissions with $10$ members each. Moreover $d_i\le9$ since $m\le85\lt91$. Let $k=|\{i:d_i\ge5\}|$. Then $$400=\sum_{i=1}^md_i\le4(m-k)+9k=4m+5k\le340+5k,$$ whence $k\ge12$; i.e., there are at least $12$ members who are on at least $5$ commissions. Choose two members $i$ and $j$ who are on at least $5$ commissions.

Case 1. There is a commission containing both $i$ and $j$.

First, there are $10$ members on the commission which $i$ and $j$ both belong to. Next $i$ belongs to $4$ more commissions, with $36$ additional members. Finally, $j$ belongs to $4$ more commissions, each of which contains at most one member of each of the $5$ commissions containg $i$, and at least $5$ members who haven't been counted yet, for a total of $20$ new members. This shows that $m\ge10+36+20=66$.

Case 2. There is no commission containing both $i$ and $j$.

In this case a similar argument shows that $m\ge67$.

This proves that $m\ge66$. Combining this with the upper bound shown earlier, we have $$66\le m\le85.$$


This post exhibits a solution with $82$ members. Combined with the excellent answer by @Song, this means $82$ is indeed optimal.

Motivation: The excellent answer by @Song and the followup comments by @Servaes make me wonder... perhaps if we look for 41 commissions (not 40) then there is a solution with a great deal of symmetry:

  • (a) 82 members (the optimal answer we seek)
  • (b) 41 commissions (exceeds OP requirement)
  • (c) each member associated with exactly 5 commissions (not part of OP)
  • (d) each commission associated with exactly 10 members (equals OP requirement)
  • (e) each 2 members have exactly 1 common commission (not part of OP)
  • (f) each 2 commissions have exactly 1 common member (exceeds OP requirement)

This would be like a finite projective plane, but with 82 points and 41 lines. However, in a finite projective (respectively: affine) plane, the no. of points and no. of lines are equal (respectively: almost equal), and this is probably why a solution based on FPP only reaches 84. So I decided to look at related structures called Block Designs, Steiner Systems, etc. where there are typically many more "lines" than "points". After quite a bit of digging, I think I found the right structure:

The solution: It is a Steiner $S(t=2,k=5,n=41)$ system. A Steiner system is defined by the following properties:

  • there are $n=41$ objects (these are the commissions)

  • there are $b$ blocks (these are the members), each block (member) being a subset of objects (i.e. the commissions he/she is associated with)

  • each block has $k=5$ objects (each member is associated with 5 commissions)

  • every $t=2$ objects is contained in exactly 1 block (every 2 commissions have exactly 1 common member)

So this already satisfies (b), (c) and (f). Next, quoting from https://en.wikipedia.org/wiki/Steiner_system#Properties we have:

  • $b = {n \choose t} / {k \choose t} = (41 \times 40) / (5 \times 4) = 41 \times 2 = 82$, satisfying (a)

  • $r = {n-1 \choose t-1} / {k-1 \choose t-1} = 40 / 4 = 10$, where $r$ denotes "the number of blocks containing any given object", i.e. the number of members associated with any given commission, satisfying (d).

Thinking more, I don't think (e) can be satisfied. However, (e) is not needed for the OP, so it doesn't matter.

So finally we just need to prove that such a Steiner $S(t=2,k=5,n=41)$ system exists. This existence is non-trivial, but luckily more digging reveals:

  • https://math.ccrwest.org/cover/steiner.html has a list of Steiner systems that are known to exist. $S(2,5,41)$ (the webpage sometimes lists the 3 parameters in different order) is not part of any infinite families listed, but if you go further down the page it is listed as a standalone example; clicking on that link goes to...

  • https://math.ccrwest.org/cover/show_cover.php?v=41&k=5&t=2 which exhibits the system, created via "Cyclic construction" whatever that means.

I did not check the numbers thoroughly, but if I understand the webpage correctly, there should be 82 rows (members / blocks), each containing 5 numbers (commissions), all the numbers being 1 through 41 inclusive (the 41 commissions), each number (commission) should appear in 10 rows, and every pair-of-numbers should appear in 1 row.

I am not an expert in any of these, so if I had a mistake or misunderstanding above, my apologies. Perhaps someone more expert can check my work?

Tags:

Combinatorics

Recent Posts