I found an interesting problem regarding the principle of inclusion and exclusion.
Given $1985$ sets, each containing $45$ items, find their total union, if the union of any two is $89$.
This is what I did:
First, I found out the intersection of any two. Using the principle of inclusion and exclusion, I managed to find out that |$A_{1}$|$\cup$|$A_{2}$|=|$A_{1}$|+|$A_{2}$|-|$A_{1}$|$\cap$|$A_{2}$|. From this, we know that $89=45+45-x$, where $x=1$. The first thing that came to my mind was that this intersection could be the common intersection of all the sets:
A solution I found to the entire problem is that there is one element that every set has in common, and 44 elements that each set does not share with no other set. To clarify, one can imagine a flower, whose petals are individual sets, their only common item being the center of the flower. Each and every pair of sets therefore contains the required 89 elements ($44$ elements on one petal $+$ $44$ elements on the other petal $+ 1$ element in the centre), each set also contains $45$ elements. Therefore, the total sum of all the elements, or the union of all the sets, is $1985\times44+1$. But I do not know how to prove this with formulas and expressions. I am also not sure whether this is correct, because of what I found when I tried to solve a similar problem but only with three sets:
The rules of this problem are exactly the same as before, only now we have $3$ sets instead of $1985$. I found out two ways to arrange the elements of the sets which satisfy the rules, each of them having a different total union.
If we had a three-set Venn diagram, one solution is this:
1 element in the intersection of them all ($A \cap B \cap C$)
44 elements in each individual set but not in any intersection (in $A$,$B$,$C$)
The other solution is this:
1 element in each intersection of every pair, but not in the intersection of them all
43 elements in each individual set.
Their unions are different, because while in the first solution, the union is $44\times3+1$, while in the second solution, the union is $43\times3+3$. These are different numbers and therefore I am unsure about my solution to the original problem. My question is whether there is an analytical way to solve this problem, or whether I am missing something.
Best Answer
Claim: There is one element that every set has in common.
Proof by contradiction. Suppose there isn't such an element.
Fix a set $A_1$.
For each element $a_{1,i} \in A_1$, let $ A_{1,i}$ denote that sets (not including $A_1$) which contain $a_{1,i}$.
The $A_{1,i}$ are disjoint from each other, so $\sum |A_{1,i}| = 1985 - 1$.
Fix an element $a_{1,i} \in A_1 $.
By the assumption, $|A_{1,i} | < 1984$, and so there is another $j\neq i$ such that $ a_{1,j} \in A_1$ and $|A_{1,j}| > 0 $.
Let $B_k \in A_{1,j}$, where $B_k$ is one of the original sets with 45 elements.
We will prove by contradiction that $|A_{1,i}| \leq 44$.
Coming back to the original claim, we have $$1984 = \sum_{i=1}^{45} |A_{1,i} | \leq 45 \times 44 = 1980,$$ which is a contradiction.