Let us first count the number of topic choices. There are 7 course and a student must choose 3 among them. Therefore there are $$ {7 \choose 3} = 35$$ such choices.
Now there are 200 students. Suppose that there are at most 5 students that have completed the same electives as each other. We have $$5\times 35 =175.$$ But $175<200$ and therefore at least 6 students have completed the same electives.
(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.
Best Answer
Consider the sequence of initial sums $S(0),S(1),\ldots,S(55)$ $$ S(n)=\sum_{i=1}^na_i. $$ We have $$S(0)=0<S(1)<S(2)<\cdots<S(55)<95,$$ a sequence of 56 distinct integers in the interval $[0,94]$ of $95$ possibilities.
Consider also the sequence of numbers $T(i)=S(i)-15$. There are 56 of those as well, all integers in the range $[-15,79]$. Because they are all distinct, at least $56-15=41$ of them are non-negative.
Hints:
Spoiler #1
Spoiler #2