Pupils of a school are divided into $112$ groups, of $11$ members each. Any two groups have exactly one common pupil. Prove that: a) there is a pupil that belongs to at least $12$ groups. b) there is a pupil that belongs to all the groups.
Problem
Source: Greece JBMO TST 2015 p4
Tags: combinatorics, set theory, Sets
29.04.2019 13:43
Isnt this just helly's theorem?
14.05.2020 22:18
Any solution with pigheonhole principle please. Or anything besides @above
25.10.2023 18:46
Let's prove that there is a person who is in at least $11$ groups. Assume contrary. Let $G_1$ has members $A_1,...,A_{11}$. They are in at most $11.10=110$ groups total other than $G_1$. So there should be a group which any $A_i$ is not in. Contradiction There is a person who is in at least $11$ groups. Assume that there is noone who is in more than $11$ groups. Let the person who is in $11$ group be $A_1$ and let $A_1$ be in the groups $G_1,...,G_{11}$. $G_1,...,G_{11}$ has a common member so there cannot be any person who is in both $G_j,G_k$ for some $1\leq j,k \leq 11$. $G_1$ has $11$ members which are $A_1,...,A_{11}$. There are $101$ groups which are not $G_1,...,G_{11}$.$A_2,...,A_{11}$ can be in at most $10.10=100$ groups other than $G_1$ which gives a contradiction. There is a person who is in at least $12$ groups. Let this person be $A$. Assume that there is a group which $A$ is not a member of it. Let that group be $G_i$ and any $12$ groups that $A$ is a member of be $G_1,...,G_{12}$. $G_i$ and $G_j(1\leq j \leq 12)$ have exactly one common person and the people are different for different $j$. There are twelve $j$ but $G_i$ has $11$ members. Contradiction
04.11.2023 08:08
Name the groups as $G_1,G_2,...,G_n$. As $G_i \cap G_j \neq \phi$, According to Helly's Theorem, We must have that $\bigcap_{i=1}^{112}{G_i} \neq \phi$, which means that there is a person belonging to all the groups, this overkills both the parts.