Question

Find the least number of cables required to connect eight computers to four printers to guarantee that for every choice of four of the eight computers, these four computers can directly access four different printers. Justify your answer.

Short answer

The resultant answer is 20 cables.

Step-by-step solution

Given data

There are 8 computers and 4 printers, are the given expression.

Concept of Pigeonhole principle

If the number of pigeons exceeds the number of pigeonholes, at least one hole will hold at least two pigeons, according to the pigeon hole principle.

Simplify the expression

It is required to connect 8 computers to 4 printers and be sure that in every group of four computers, all printers can be accessed.

Note that it is not required for every computer of every group of four computers to necessarily have access to one or more printers.

First connect 4 of the computers to all 4 printers.

This will require \(4 \cdot 4 = 16\) cables.

Now there is only one group of four computers that has no access to the printers.

Take one of them and connect to all the printers, which will require further \(4 \cdot 1 = 4\) cables.

Thus, \(16 + 4 = 20\) cables in total are needed.

Hence, the resultant answer is 20 cables.