Show that every person gets a suitable job

138 Views Asked by At

There are $n\geq 4$ people who've come for jobs. It's known that the $i^\text {th}$ can do $j_i$ many jobs. If there's a $\geq n$ vacancy for jobs and $$\frac{1}{j_1}+\frac{1}{j_2}+\frac{1}{j_3}+\cdots + \frac{1}{j_n} < 1$$ then each person gets a suitable job

.

I am not sure exactly how to do this but as I can guess from my counterexamples, there's something like probability of the work a person gets works somehow I feel.

2

There are 2 best solutions below

0
On BEST ANSWER

Let $J_n = \max(j_1, ..., j_n)$. Then $\frac{1}{j_1} + \ldots + \frac{1}{j_n} \geq \frac{n}{J_n}$ so we must have $J_n \gt n$ if we have $\frac{1}{j_1} + \ldots + \frac{1}{j_n} \lt 1$.

Hence at least one person (let's say the $n$-th person) is capable of doing more than $n$ jobs. So if we assign a job to everyone else, it is guaranteed that this person will still have a suitable job.

Thus the problem is reduced to knowing whether we can assign each of the $n-1$ remaining persons a job given that $\frac{1}{j_1} + \ldots + \frac{1}{j_{n-1}} \lt 1$.

By a similar argument we find $J_{n-1} = \max(j_1, \ldots, j_{n-1}) \gt n-1$ hence if we assign a job to each of the first $n-2$ persons, we can find a job for the $n-1$-th person.

An inductive argument should allow you to continue down to the base case $n = 1$.

0
On

Use the Hall maximal matching theorem.

Let $P$ be the set of persons and $J$ the set of available jobs. Then each person $P_k$ is connected with at least $j_k$ jobs in $J$.

Now take any subset $X$ of persons in $P$ and let $N(X)$ be the set of all jobs they are connected to. We have to prove that $|X|\leq |N(X)|$. Let $X=\{P_1',P_2'...P_k'\}$ and we can assume that $j_1'\leq j_2'\leq ...\leq j_k'$. Then $ |X|=k$ and we have $${k\over j_k'}\leq \frac{1}{j_1'}+\frac{1}{j_2'}+\cdots + \frac{1}{j_k'} \leq \frac{1}{j_1}+\frac{1}{j_2}+\cdots + \frac{1}{j_n} < 1$$ So $k< j_k'$. But $j_k' \leq |N(X)|$ so $|X|\leq |N(X)|$ and we are done.