(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.
The pigeonhole principle is basically a counting argument that says if you have n items to put into m pigeonholes with n > m, at least on pigeonhole must contains more than one item.
In this particular case, there are 9 students (items) and 2 pigeonholes (genders), so when you have assigned gender to 8 students, you either already have a group (pigeonhole) with 5 students of the same gender, or you have two groups, each with four students. Therefore, regardless of the gender of the 9th student, one of the groups must end up with 5.
Similarly, after you've assigned gender to 6 students, either there were already 3 males, or there were 0, 1 or 2 males. You still have 3 more students, so if there were 0 males, there must have been 6 females, and either the 3 remains students are all males (in which case, there will be 3 males) or one of the is a female (in which case, there will be at least 7 females). The argument for 1 or 2 males out of the 6 is similar.
Best Answer
If you take $50\times 99$ students ($99$ by state), you are sure to have at least $99$ students coming from each state. If you add $1$, whatever the state he comes from, you are sure there are $100$ students coming from the same state (and there is only one state from which $100$ students come).