I got three questions while writing some exercises.


(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?

  • $\begingroup$ You write: "I know this can't be proved by pigeonhole principle, but how can I prove it?" Why do you know this? $\endgroup$ – Thomas Andrews Oct 26 '12 at 14:28
  • $\begingroup$ @Thomas: I think that can’t is a typo for can. $\endgroup$ – Brian M. Scott Oct 26 '12 at 15:03
  • $\begingroup$ @BrianM.Scott: No, I didn't type that can't wrong. I thought the sum should be limit between 1 and 69 since 1 is the smallest postitive integer. Thus the 62 possible subsets will not be able to cover the range of the sum. So I think it can't be proved by pigeonhole principle. $\endgroup$ – lucasKo Oct 27 '12 at 14:52

(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.

  • $\begingroup$ @lucasKoFromTW: You’re welcome. $\endgroup$ – Brian M. Scott Oct 27 '12 at 14:55
  • $\begingroup$ when you have computers $C_{1}$, $C_{2}$, $\cdots$, $C_{m}$ and $P_{1},\cdots ,P_{m}$ with $C_{k}$ connected to $P_{k}$ for $k=1,\cdots ,m$, do you mean that each $C_{i}$ is connected to $P_{i}$ and only to $P_{i}$? Or do you mean $$\text{for}\,i =1\cdots m\, \text{do} \\ \text{for}\,k=1,\cdots , m\, \text{do}\\ C_{i}\to P_{k} \\ k+1 \\ \text{end when}\, k+1>m\\ i +1\\ \text{end when }\, i +1>m$$? As in, is each computer in the subset matched to every printer? From your use of the same indices for the computers and the printers, that part was unclear. $\endgroup$ – user100463 Feb 5 '18 at 15:58
  • $\begingroup$ also, when $n=m$, do you mean that each computer is connected to one and only one computer when you say you need only $m$ cables? $\endgroup$ – user100463 Feb 5 '18 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.