5
$\begingroup$

Consider the $35$ sets $A_1,A_2,\dots,A_{35}$ such that $|A_i|=27$ for all $1\leq i \leq 35$, and every triplet of sets have one exactly one element in common to all three. Prove that there is at least one element common to all $35$ sets.

This was a problem given to me by a friend - he asked me to help him with this but I am unable to figure out the answer. He suggested something about contradiction and the pigeonhole principle, but I'm not sure how to continue. He mentioned it was from some sort of Olympiad, but I dont remember which one (something middle eastern?)

I found this similar question online: https://artofproblemsolving.com/community/q1h1699161p10908761

but this doesn't include any restrictions on cardinality, and is only a case for a pairwise disjoint set.

$\endgroup$
  • 1
    $\begingroup$ "...such that $| A_i|=27$ for all $1\leq i\leq 27$..." Is this a typo? Should it be $1\leq i\leq 35$ instead? $\endgroup$ – YiFan Nov 22 '18 at 23:04
  • $\begingroup$ @YiFan Yes, fixed, thank you $\endgroup$ – user574848 Nov 22 '18 at 23:14
  • $\begingroup$ Consider A$_1$. There are $\binom{34}{2}$= 561 triplets of sets that include A$_1$. BY the pigeonhole principle there is at least 1 element of A$_1$ that is shared by 20 of these triples. Maybe you can keep reducing the problem accordingly. $\endgroup$ – Joel Pereira Nov 23 '18 at 0:09
3
+50
$\begingroup$

Lets assume there is no element common to all 35.

Any set $A_i$ is part of $\binom{34}{2} = 561$ triplets. $A_i$ has 27 items. $ 27 \cdot 20 = 540 < 561 $, so from the pigeonhole principle some item a in $A_i$ must be in 21 of the triplets. This means that at least 7 other sets must include a, since $\binom{7}{2} = 21$. In turn, this means that a is in at least 8 sets (including $A_i$). Among these sets, there are $\binom{8}{2} = 28$ pairs.

Lets assume some set $A_j$ does not contain a. $A_j$ must have some item in common with every one of the $28$ pairs.

If an item b is common to $A_j$ and two subsets that contain a, it must not be in any other subset that contains a, since each triplet has only one item in common, so no three sets that include a can share the item b.

This means there must be at least 28 unique elements in $A_j$, but this is impossible since $|A_j| = 27$.

So a must be common to all sets $A_j$, in contradiction to the assumption.

$\endgroup$
  • $\begingroup$ Nice proof ! Allow me to suggest an edit : since at the beginning of your proof what you're really doing is fixing an $i$ and not reasoning on all $i$ at once, I think it would be slightly more readable if you put : "$A_1$ is part of 561 triplets and has 27 items , etc." $\endgroup$ – Ewan Delanoy Nov 23 '18 at 11:52

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.