All members of the senate were firstly divided into $S$ senate commissions . According to the rules, no commission has less that $5$ senators and every two commissions have different number of senators. After the first session the commissions were closed and new commissions were opened. Some of the senators now are not a part of any commission. It resulted also that every two senators that were in the same commission in the first session , are not any more in the same commission. (a)Prove that at least $4S+10$ senators were left outside the commissions. (b)Prove that this number is achievable. Albanian National Mathematical Olympiad 2010---12 GRADE Question 5.
Problem
Source:
Tags: pigeonhole principle, combinatorics unsolved, combinatorics
06.03.2011 12:52
(a) The first division in commissions has $5\leq c_1 < c_2 < \ldots < c_S$ members in the $S$ commissions, thus $c_k \geq k+4$ for $1\leq k \leq S$. The total number of members is therefore $N \geq \sum_{k=1}^S (k+4) = \dfrac {(S+4)(S+5)} 2 - 10$. After the second division, no new commission may have more than $S$ members, thus the total number of members of the new commissions is $M \leq \sum_{k=5}^S k = \dfrac {S(S+1)} 2 - 10$. Therefore $N - M \geq \left (\dfrac {(S+4)(S+5)} 2 - 10\right ) - \left (\dfrac {S(S+1)} 2 - 10 \right ) = 4S + 10$ senators are left outside the new commisions. (b) This bound can be achieved. Take $c_k = k+4$ for $1\leq k \leq S$. Remove $4$ senators from each commision, thus putting $4S$ senators on the side. Build new commissions by taking one each senator from each old commission - this will create new commissions with $S, S-1, \ldots, 5$ members, and there will be $1+2+3+4=10$ more senators left out.
10.05.2012 17:07
(a) We sort the commissions by increasing number of members. Then from the conditions the first commission must have at least $5$ members, the second $6$, ..., the last $5+S-1$, for a total of at least $5+6+\cdots +(5+S-1)=\frac {S^2+9S} 2$ members; on the other hand, each new commission may have, by the pigeonhole principle, at most $S$ members, for otherwise at least one commission would have two members which previously were in the same commission, and so the maximal number of members is $S+(S-1)+\cdots +5=\frac {S^2+S} 2-10$. This accounts for at least $\left ( \frac {S^2+9S} 2 \right )-\left ( \frac {S^2+S} 2-10 \right )=4S+10$ members left outside. (b) To have equality, create commissions with $5$, $6$, ..., $S+4$ members in the first round, then remove four senators from each commission, then for $5 \leq i \leq S$ put one senator of each commission which previously had $i$ members in each of the new commissions from $S-i+5$ to $S$, letting out the ten last members.
31.07.2018 19:34
What about $S=1$, and we have $5$ senators? At most $5$ senators can be left out. But $5<10<4S+10$... In the second commissioning, there just aren't any commissions.