2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ The claim that "there is one element that every set has in common and 44 element that each set does not share with no other set" rests on the fact that $1985 > 45 \times 44$. When you have 3 sets, this inequality isn't satisfied, and there can be numerous other configurations (like what you listed). $\endgroup$ – Calvin Lin Oct 29 '20 at 20:42
  • $\begingroup$ @CalvinLin Thank you for your answer, but I am not sure whether I understand. Why is it important that the number of all the sets is bigger than 45 times 44? Or, rather, I am not sure whether my original solution is correct. $\endgroup$ – ampersander Oct 29 '20 at 20:52
  • $\begingroup$ What is your "original solution"? You found a "possible construction", but haven't proven that it is the "only possible construction". So, as a proof question, this is worth 0+. But as a numerical question, you'd get full credit. $\endgroup$ – Calvin Lin Oct 29 '20 at 20:53
  • $\begingroup$ It was a numerical question, the problem's task was to find the value of the union of any possible construction. it was only my curiosity that made me think whether there are more solutions. I am unsure about how to make a proof of more constructions, that is why I asked in here. Also, sorry for my english, it's not my mother tongue and translating mathematical concepts gets kinda tricky $\endgroup$ – ampersander Oct 29 '20 at 20:58
  • $\begingroup$ IMO it's not a great numerical question, since it's easy to find a construction, but it's hard to prove that it's the only construction. I've added an explanation for why the claim is true when there are $\geq 45 \times 44 + 2$ sets. $\endgroup$ – Calvin Lin Oct 29 '20 at 21:01
3
$\begingroup$

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$.

Suppose not, so$ |A_{1,i}| \geq 45$. Then $B_j \backslash \{ a_{1,j}\} $ has 44 elements, and doesn't contain $a_{1,i}$.
So $B_k$ cannot intersect the 45+ sets in $A_{1,i}$, which are distinct sets after excluding $a_{1,i}$, which is a contradiction.
This shows 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.

$\endgroup$
7
  • $\begingroup$ I take it that $A_j$ is simply some member of $A_{1,j}$? And it’s crucial that the members of $A_{1,i}$ are not just distinct after excluding $a_{1,i}$, but are in fact pairwise disjoint. $\endgroup$ – Brian M. Scott Oct 29 '20 at 21:12
  • $\begingroup$ Thank you for your answer, but I am afraid I still have some questions. This notation you have used is new to me: $a_{1,i}$ means "every element from a1, a2, a3, ..., to ai? For each element a1,i in A1 - this means that A1 contains every alement from a1 to ai? $\endgroup$ – ampersander Oct 29 '20 at 21:15
  • $\begingroup$ @BrianM.Scott Yes, I see the confusion and have renamed it to $B_j$. Yes, the elements are pairwise disjoint since any 2 sets intersect at one element, so no set other than $A_1$ contains both $a_{1,i}$ and $a_{1,j}$. $\endgroup$ – Calvin Lin Oct 29 '20 at 22:34
  • $\begingroup$ @ampersander No, $a_{1,i}$ is an element in $A_1$. Hence the 1 in the first index. (The rest of your comment is irrelevant). $\endgroup$ – Calvin Lin Oct 29 '20 at 22:34
  • $\begingroup$ @CalvinLin: Thanks; I was pretty sure that that was the argument that you were making. (+1) $\endgroup$ – Brian M. Scott Oct 29 '20 at 22:35
0
$\begingroup$

Fix set $B=\{b_1,...,b_{45}\}$ and let $d_i$ be a number of other sets element $b_i$ is in it and let $d$ be a maximal $d_i$.

Then we have: $1984 =\sum_{i=1}^{1984}|A_i\cap B| \leq 45\cdot d \implies d\geq 45$. Thus there is an element $b$ in $B$ which appears at least in $46$ sets, say $A_1,A_2,...,A_{46}$ (one of them is $B$) and suppose there is a set $A=\{a_1,...,a_{45}\}$ which does not contain $b$.

Now for each $j\leq 46$ there is $a_i$ such that $a_i\in A_j\cap A$ and $a_i\ne b$. But then some $a \in A$ would be common to some $A_p$ and $A_q$ which means they have $2$ common elements. A contradiction, so $b$ apperas in every set.

Now by PIE we have:

$$n = 1985\cdot 45-{1985\choose 2} + {1985\choose 3} - {1985\choose 4}+..+{1985\choose 1985} $$

$$ n=1985\cdot 45 -(1-1)^{1985} +1-1985 = 1985\cdot 44+1$$

$\endgroup$

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.