Each student chooses $1$ math problem and $1$ physics problem among $20$ math problems and $11$ physics problems. No same pair of problem is selected by two students. And at least one of the problems selected by any student is selected by at most one other student. At most how many students are there?
Problem
Source: Junior Turkish Mathematical Olympiad 2011 P4
Tags: graph theory, combinatorics proposed, combinatorics
02.07.2012 20:59
Let a finite bipartite graph made of shores $M$(ath) and $P$(hysics), with $m=|M| \geq 2$ and $p=|P|\geq 2$. Each student is an edge in this graph. The condition is that, if the degree of one end of any edge is at least $3$ then the degree of the other end of the edge is at most $2$. The maximum number of edges is $2(m-2) + 2(n-2) = 2(m+n-4)$, realized for all vertices in $M\setminus \{m_1,m_2\}$ being connected by edges to $p_1, p_2 \in P$, and all vertices in $P\setminus \{p_1,p_2\}$ being connected by edges to $m_1, m_2 \in M$.
14.07.2018 23:06
Bumping but is there any non-graph theory solution?
08.01.2019 18:03
We say a problem is "unpopular" if at most 2 students choose it. Otherwise, we say the problem is "popular". The condition specifies that every student must at least choose an "unpopular" problem. First, we show it is possible to have 54 students. Let the math problems be $m_i, i=1, ..., 20$. Let the physics problems be $p_j, j=1, ..., 11$. Then, 9 students choose the same $m_1$ and a different $p_3, p_4$ to $p_{11}$ respectively; 9 students choose the same $m_2$ and a different $p_3, p_4$ to $p_{11}$ respectively; 18 students choose the same $p_1$ and a different $m_3, m_4$ to $m_{20}$ respectively; and 18 students choose the same $p_2$ and a different $m_3, m_4$ to $m_{20}$ respectively. Suppose more than 54 students is possible. If all math problems are "unpopular", there are only $20\times 2=40$ students. If exactly 19 math problems are "unpopular", then exactly one math problem is "popular", and at least $54-19\times 2+1=17$ students choose it. But every math problem can be chosen by at most 11 students, because there are only 11 physics problems. So there are at most 18 "unpopular" math problems. Similarly, there are at most 9 "unpopular" physics problems. Then, at most $18\times 2=36$ students choose the "unpopular" math problems. As for the "popular" math problems, any student who chooses them must also choose the "unpopular" physics problems, so there are at most $9\times 2=18$ students. But $36+18$ is only $54$. So the maximum number of students is 54.