นักเรียน 40 คน

[ฟินิกซ์เหินฟ้า]

นักเรียน $40$ คน ตอบคำถาม $4$ ข้อ ซึ่ง $25$ คน ตอบข้อแรกถูก และ $30,35,33$ คน ตอบข้อ
$2,3,4$ ถูกตามลำดับ จงพิสูจน์ว่ามีอย่างน้อย $3$ คน ซึ่งตอบคำถามถูก $4$ ข้อ

[Anton]

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