The jury of an Olympiad has $30$ members in the beginning. Each member of the jury thinks that some of his colleagues are competent, while all the others are not, and these opinions do not change. At the beginning of every session a voting takes place, and those members who are not competent in the opinion of more than one half of the voters are excluded from the jury for the rest of the olympiad. Prove that after at most $15$ sessions there will be no more exclusions. (Note that nobody votes about his own competence.)
Problem
Source: Baltic Way 1996 Q18
Tags: induction, combinatorics unsolved, combinatorics
Myth
22.02.2005 20:12
Specially for Pascual By induction: if we have $2n$ men, then thre are at most $n$ voitings. Suppose the contrary. Let $a_1$, $a_2$, ..., $a_{n}$ be number of people excluded after 1st, 2nd, ..., 15th voiting respectively. Let $b_i$ be number of competences from non-excluded people after 1st, ..., (i-1)th voiting, which posses man excluded in $i$-th voiting. If $a_1\geq 2$ then, obviously, we are done. So we will assume $a_1=1$. Consider the man $A$, which was excluded in $i$-th voiting. Since he wasn't excluded in $i-1$th voiting we conclude \[b_i+a_{i-1}\geq \frac{2n-a_1-a_2-...-a_{i-2}}{2},\] but as he was excluded in $i$th voiting we can write \[b_i<\frac{2n-a_1-a_2-...-a_{i-1}}{2}.\] It follows \[\frac{2n-a_1-a_2-...-a_{i-1}-1}{2}\geq b_i \geq \frac{2n-a_1-...-a_{i-2}-2a_{i-1}}{2}.\qquad \eqno (1)\] It is clear there are $i$ s.t. $n\geq i-1\geq 2$ and $a_{i-1}=1$ (otherwise after $n$ votings there is at most 1 man in jury, and he cannot be excluded). Let $m>2$ be minimal such $i$. From $(1)$ we conclude $b_{m}=\frac{2n-a_1-a_2-...-a_{m-1}-1}{2}$, so $a_1+a_2+...+a_{m-2}$ is even. Due to choice of $m$ it means $a_1+...+a_{m-2}\geq 2(m-2)$. And, obviously, we are done.