2
$\begingroup$

Recently I solved this following problem using greedy algorithm.

There are $100$ students who participate at exam.Also there are $25$ members of jury.Each student is checked by one jury.Known that every student likes $10$ jury. Prove that we can make this every student will be checked by the jury that he likes and every jury will check at most $10$ students.

Here is my solution.

Denote $A_i \; (1 \le i \le 25)$ be the set of students that like $i$th jury and $|A_i|=a_i$.

WLOG, assume that $a_1 \le a_2 \le \cdots \le a_{25}$. We start from $1$st jury to $25$th jury, each time pick $10$ students that like that jury, and must follow the following greedy algorithm:

  1. If after we pick $10$ students from $A_i$, there still $k \le A_i-10$ students (that like $i$-th jury) left that haven't been picked. We put these students into a set $S$ in order, the latest students at the left. For example, $S= \{ G_1,G_2, \cdots , ... , G_{25} \}$ where $G_i$ is the left over students after picking $10$ from $a_i$ in $i$th jury.
  2. After we pick, we exclude the jury and the students being picked (take them out from all the sets $A_i$). After excluding juries and students, we rearrange the $A_i$ and pick all the juries so $|A_j| \le 10$. This will lead to either we prove the statement or the juries left all have $|A_j| \ge 11$.
  3. After finishing picking $A_{i}$, we move to pick students that like $i+1$th jury in $A_{i+1}$, but our priority is to pick as much students in $A_{i+1} \cap S$ as possible, and if there is still $h \le 10$ more students need to pick, then we pick arbitrary from $A_{i+1} \setminus S$. Remember to pick $A_{i+1} \cap S$ in order from oldest to latest (which means from $G_1$ to $G_{25}$).

Now, we need to guarantee that with this, we can always make every students be checked by the jury he/she likes. The worst case scenario is that at some point, there will be a student $X$ remaining that doesn't like any jury remaining. If that happens, consider $10$ juries that $X$ likes, denote their set to be $B_i \; (1 \le i \le 10)$ with $|B_i|=b_i$ and $b_1 \le b_2 \le \cdots \le b_{10}$. This means $10<b_i$ (otherwise $X$ will be picked by some $i$th jury with $b_i \le 10$).

Condition 2 of the algorithm guarantees that we can always bring back to a situation that all the juries have $|B_i| \ge 11$.

Next, after jury with $B_1$ picks students, then student $X$ must be left out so $X$ is in $S$. After jury with $B_2$ picks students, since out priority is $B_2 \cap S$, so there must be exactly $10$ students + student $X$ who like jury $B_2$ in $S$ (from condition 2 and optimal picking of $B_2 \cap S$ in condition 3). After picking $B_2$, those $10$ students that like $B_2$ will be picked, hence similarly, there will be $10$ more students in $S$ that like jury $B_3$. If there is no jury $A_j$ between $B_i,B_{i+1}$ (means $|B_i| \le |A_j| \le |B_{i+1}|$) then this will continue until jury with $B_{10}$ and we find that $|S| \ge 10\cdot 9+1=91$ at stage after picking students for jury $B_1$. This is obviously a contradiction since $|B_1| \ge 11$ so that means after picking $10$ students that likes jury $B_1$, we must have $|S| \le 90$.

If there is a jury $A_j$ between some $B_i,B_{i+1}$ then from the oldest to latest rule in condition 3, we find that this won't affect that $|S| \ge 91$ at stage picking $10$ from $B_1$ (otherwise, if there is no $10$ students that like $B_{i+1}$ in $S$ at stage after picking $10$ from $B_1$, according to oldest, latest rule, we must pick student $X$ who like $B_{i+1}$ because $X$ is in older group).

Thus, the scenario that student $X$ can't find jury he/she like cannot happen. In other words, this algorithm works. $\square$

My main question is:

Is this solution correct?

Comment. For a) by using Probabilistic method, we can guarantee picking $8$ juries so each student likes at least one jury. Indeed, pick $8$ juries randomly, the probability that a student doesn't like all $8$ juries is $\frac{\binom{15}{8}}{\binom{25}{8}}$. Hence, if $X$ be the number of students that don't like all $8$ juries, according to Linearity of Expected value, we have $\mathbb{E}[X]= 100 \cdot \frac{\binom{15}{8}}{\binom{25}{8}}<1$. Thus, there exists way to pick $8$ juries so $\mathbb{E}[X]=0$, or no students that don't like all $8$ juries. I don't think probabilistic method can't prove for $7$ juries because $100 \cdot \frac{\binom{15}{7}}{\binom{25}{7}} >1$.

$\endgroup$
1
  • $\begingroup$ @JohnWatson (a) is Prove that we can select $7$ jury such that any student likes at least one jury. $\endgroup$
    – Tengu
    Oct 11, 2017 at 20:27

2 Answers 2

3
+50
$\begingroup$

I read your proof and I believe it is correct.

As a minor nit, it isn't right to say the algorithm will "each time pick $10$ students" - it might pick fewer in step 2.

The argument can be simplified substantially. Once you have defined $b_1,\dots,b_{10}$, we know there must have been $10$ other students picked from each $B_i$ instead of student $X$. That makes $100$ other students picked. But together with $X$ that makes at least $101$ students, more than the total student population.

Note the proof of correctness then doesn't even depend on any kind of ordering or prioritizing $S$ - you can just repeatedly pick any juror, assign as many students as possible to that juror, remove all the assigned people, and repeat until done.


For the bonus question (a), you can argue as follows:

  • For any $100$ students each liking $10$ of $25$ jurors, some juror is liked by at least $\lceil 10 * 100 / 25\rceil = 40$ students, leaving at most $60.$
  • For any $60$ students each liking $10$ of $24$ jurors, some juror is liked by at least $\lceil 10 * 60 / 24\rceil = 25$ students, leaving at most $35.$
  • For any $35$ students each liking $10$ of $23$ jurors, some juror is liked by at least $\lceil 10 * 35 / 23\rceil = 16$ students, leaving at most $19.$
  • For any $19$ students each liking $10$ of $22$ jurors, some juror is liked by at least $\lceil 10 * 19 / 22\rceil = 9$ students, leaving at most $10.$
  • For any $10$ students each liking $10$ of $21$ jurors, some juror is liked by at least $\lceil 10 * 10 / 21\rceil = 5$ students, leaving at most $5.$
  • For any $5$ students each liking $10$ of $20$ jurors, some juror is liked by at least $\lceil 10 * 5 / 20\rceil = 3$ students, leaving at most $2.$
  • For any $2$ students each liking $10$ of $19$ jurors, some juror is liked by at least $\lceil 10 * 2 / 19\rceil = 2$ students, leaving none.
$\endgroup$
0
$\begingroup$

I wonder if the following is correct proof? Can someone check please. (I need a jury!)

Take first $25$ students. Take any subset $X$ of this students and let $Y$ be the set of jury the students in $X$ like. Then since each student likes exactly $10$ jury and each jury checks at most $10$ students, we have for $ 10|X|\leq 10|Y|$ so $|X|\leq |Y|$ and Hall condition is fulfilled and thus we have a perfect matching. So each jury checks exactly 1 student.

We repeat this with next $25$ students and again we have perfect matching. So now each jury checks exactly $2$ students. We repeat this two more times, so each jury checks exactly $4<10$ students and each student is checked by jury he likes.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .