I am having a difficult time with understanding this problem:
The computer classroom has 12 PCs and 5 printers. What is the minimum number of connections that must be made to guarantee that any set of 5 or fewer PCs can access printers at the same time?
The answer the book gave me is 40 connections, but I do not know how it came up with the answer. Any guidance will help. Thank you!
To avoid just giving you the answer, let me assume there are 10 PCs with 4 printers. Let me label the PCs $C_{1}, C_{2}, \ldots, C_{10}$ and the printers by $P_{1}, P_{2}, P_{3}, P_{4}$. We connect them as follows:
$$\begin{align} C_{1} &\;\longleftrightarrow\; S_{1} \\ C_{2} &\;\longleftrightarrow\; S_{2} \\ C_{3} &\;\longleftrightarrow\; S_{3} \\ C_{4} &\;\longleftrightarrow\; S_{4} \\ C_{j} &\;\longleftrightarrow\; S_{1}, S_{2}, S_{3}, S_{4} \end{align}$$
for $5\leq j \leq 10$. Thus all computers are connected to at least one printer and there are 28 connections in total. It should be obvious with a bit of thought that any set of 4 or fewer computers can now simultaneously access a printer. We can now use the pigeonhole principle to show this is actually the minimum number:
Assume there are fewer than 28 connections, then some printer would be connected to at most $\lfloor 27/4 \rfloor = 6$ computers. This means the remaining 3 printers are not enough to allow the other 4 computers to simultaneously have access to different printers. Therefore at least 28 connections are needed.