อ้างอิง:
|
Problem. Forty students answered four questions. It is known that $25$ students answered the first question correctly, $30$ answered the second question correctly, $35$ answered the third question correctly, and $33$ answered the fourth question correctly.Show that there are at least three students who answered all four questions correctly.
|
Let $G$ be a bipartite graph whose vertices can be partitioned into two sets $S$ and $Q$, where $S$ is the set of $40$ students and $Q$ is the set of $4$ questions. There exists an edge between $s\in S$ and $q\in Q$ if and only if the student $s$ answered the question $q$ correctly. There are no other edges in $G$.
We know that the number of edges in $G$ is equal to
$$\sum_{q\in Q}\,\deg(q)=25+30+35+33=123\,.$$
Suppose that exactly $k$ students answered all four questions correctly. Therefore,
$$123=\sum_{s\in S}\,\deg(s)\leq 4k+3(40-k)=120+k\,.$$
This shows that $k\geq 3$.