Each cable forms a direct connection between a single computer and a single printer. Communication through multiple cables is not considered as "direct connection".
Find the fewest number of cables to connect 8 computers and 4 printers such that:
Given any selection of 4 computers, each computer has a direct connection with a distinct printer.
Note: For each printer (resp. computer), there is no limit to the number of computers (resp. printers) that it can be directly connected to.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
First, I claim that 2 0 cables work.
Number the computers 1 , 2 , … , 8 and the printers 1 , 2 , 3 , 4 . Connect computer i to printer i for all i ∈ { 1 , 2 , 3 , 4 } . Connect the four other computers to all four printers. Now, given four selected computers, process the first four computers first: they have only one printer to go. The remaining computers have free choices, and can obviously be fitted to all printers.
Now, I claim that 1 9 cables doesn't work.
By Pigeonhole Principle, with 1 9 cables and 4 printers, one printer is connected to at most 4 computers. Pick four computers not connected to this printer. They collectively cannot use this printer, so there are four computers and three printers, impossible to complete.