There are $40$ members of jury, that want to choose problem for contest. There are list with $30$ problems. They want to find such problem, that can be solved at least half members , but not all. Every member solved $26$ problems, and every two members solved different sets of problems. Prove, that they can find problem for contest.
Problem
Source: St Petersburg Olympiad 2009, Grade 9, P2
Tags: combinatorics
30.08.2017 15:17
20.02.2018 19:51
17.02.2021 18:13
Good problems
17.02.2021 18:14
Hopeooooo wrote: Good problems 1. please dont postfarm 2. please dont bump three-year-old threads.
15.04.2021 19:28
08.12.2022 02:03
Assume that such a problem doesn't exist. Call a problem easy if it was solved by all jury members, and denote the number of easy problems by $e.$ Then the inequality $$40e +19(30-e) \geq 40 \cdot 26= 1040$$must hold by considering the number of total problems solved in two ways. This means that $e \geq 23.$ But this means that every member of the jury has solved $26-e$ problems which were not easy and there are $\binom{30-e}{26-e} \leq \binom{7}{3}= 35 < 40$ possible ways to solve these $26-e$ problems. However, this implies that two people have solved the same set of problems since this set only depends on the solved problems which were not easy.