I got three questions while writing some exercises.
Questions
(1) Suppose S is a set of 6 positive integers, whose maximum is 14. Prove that the sums of elements in all non-empty subsets of S cannot be different to each other.
I know this can't be proved by the pigeonhole principle, but how can I prove it?
(2) Prove that, within a group of 6 people, there must be either three people who all know each other or three who don't.
This seems to be a general question, but I still can't figure it out.
(3) Find the least number of cables required to connect $n$ computers to $m$ printers to guarantee that any $m$ computers can direct access $m$ different printers.
The reference answer says it will be $m + (n – m)m$. This is correct, but how can I get it in the first place?
Best Answer
(1) $S$ has $2^6$ subsets; one of them is the empty set, so $S$ has $2^6-1$ non-empty subsets. We know that $\max S=14$; let $m=\min S$. Then the largest possible sum of numbers in a non-empty subset of $S$ is $$14+13+12+11+10+m=60+m\;,$$ and the smallest possible sum is $m$. The possible sums are therefore all in the set $\{m,\dots,60+m\}$; how many numbers are in this set? How does that compare with $2^6-1$?
(2) This is sometimes called the theorem on friends and strangers; see the link for a proof.
(3) Are you asking how one might discover the formula $m+(n-m)m$? Here’s one possibility. If $n=m$, it’s clear that connecting each computer to a different printer does the job with $m$ cables, and we certainly can’t use fewer than $m$ cables. Say that we have computers $C_1,\dots,C_m$ and printers $P_1,\dots,P_m$, with $C_k$ connected to $P_k$ for $k=1,\dots,m$. Now we add another computer, $C_{m+1}$. Consider the $m$-set of computers $\{C_2,\dots,C_{m+1}\}$; in order for it to be connected to all $m$ of the printers, $C_{m+1}$ must be connected to $P_1$. Similar reasoning shows that $C_{m+1}$ must be connected to each of the printers, so we end up using $m+1\cdot m$ cables. Of course it’s conceivable that we could do better if we modified the original cabling, but nothing better is immediately apparent, so we continue: we add $C_{m+2}$. The same reasoning as before shows that if we leave the existing cables in place, we need to add cables from $C_{m+2}$ to each of the printers, and it’s not hard to check that this is sufficient. Thus, we end up with $m+2\cdot m$ cables. At this point it’s fairly clear that if we connect every new computer to all of the printers, the condition will be satisfied, and doing so will require $m+(n-m)m$ cables: the original $m$, plus $m$ for each of the $n-m$ extra computers. Since no better solution is apparent, the next step is to try to prove that $m+(n-m)m$ actually is the minimum; we’ve shown that it suffices, but we still have to prove that no smaller number of cables will do the job.
This is where something like the pigeonhole principle comes in. Suppose that there are fewer than $m+(n-m)m$ cables. Then on average each printer is connected to fewer than $$\frac{m+(n-m)m}m=1+n-m$$ computers, so there is at least one printer that is connected to fewer than $1+n-m$ computers. Let $P$ be such a printer; $P$ is connected to at most $n-m$ computers, so there there are at least $m$ computers to which $P$ is not connected. Let $\mathscr{C}$ be a set of $m$ computers that are not connected to $P$; then the computers in $\mathscr{C}$ can access at most $m-1$ computers, and the condition is not satisfied. Thus, a cabling that uses fewer than $m+(n-m)m$ cables cannot work.