In a test, $201$ students are trying to solve $6$ problems.We know that for each of $5$ first problems, there are at least $140$ students, who can solve it. Moreover, there is exactly $60$ students, who can solve $6^{th}$ problem. Show that there exist $2$ students, such that two of them combined are able to solve all $6$ question. (For example, number $1$ do $1,2,3,4$ and number $2$ do $3,5,6$)
Problem
Source: Thailand TSTST 2024 P7
Tags: combinatorics
19.07.2024 19:05
Don't know if there is an official solution anywhere, but here is my attempt. If any one student solves all problems 1 through 5, then we are done because we can pair that student with anyone who solved problem 6. In general, if we know that some subset of $m$ students has a total of at least $4m + 1$ solves among problems 1 through 5 (think of each solve as a (student, problem) pair), then one of these $m$ students must have solved all of problems 1 through 5, so we would be done. Even more generally, if we know that some subset of $m$ students has a total of at least $(p-1)m + 1$ solves among a subset of $p$ problems, then one of these $m$ students must have solved all $p$ problems in that subset. Call a set of two students a spanning pair if they collectively solve all of problems 1 through 5. It suffices to show that at most $59$ of the $201$ students are NOT part of a spanning pair, since this guarantees that one of the $60$ solvers of problem 6 is in a spanning pair of students, who collectively solve all six problems. For $m = 201$ and $p \in \{0, 1, 2, 3\}$, any subset $P$ of $p$ problems from problems 1 through 5 must have at least $140p$ solves among the $m$ students; since $140p \geq (p - 1)m + 1$ for each of these values of $p$, by the above reasoning there must be some student who solved all problems in $P$. Therefore, any student who solved at least two of the first five problems must be in a spanning pair because the subset of problems 1 through 5 that they did not solve must have been fully solved by some other student. Let $k$ be the number of students who solved at most one of the first five problems, which is an upper bound on the number of students NOT in a spanning pair. Then, the other $201 - k$ students have a total of at least $140\cdot 5 - k = 700 - k$ solves among the first five problems. From our earlier argument, if $700 - k \geq 4(201 - k) + 1$, then one of these $201 - k$ students must have solved all of the first five problems, so we would be done. By the logical equivalence $$700 - k \geq 4(201 - k) + 1 \iff 699 \geq 804 - 3k \iff 3k \geq 105 \iff k \geq 35,$$we are done in this fashion whenever $k \geq 35$. When $k < 35$, we conclude that there are fewer than $35$ students who are not in a spanning pair, so we are also done.
15.10.2024 10:27
Using double counting on incidence matrix