Question

Find the least number of cables required to connect 100 computers to 20 printers to guarantee that 2 every subset of 20 computers can directly access 20 different printers. (Here, the assumptions about cables and computers are the same as in Example 9.) Justify your answer.

Short answer

The resultant answer is 1620 cables.

Step-by-step solution

Given data

There are 100 computers and 20 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 100 computers to 20 printers and be sure that in every group of twenty computers, all printers can be accessed.

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

First connect 80 of the computers to all 20 printers. This will require \(80 \cdot 20 = 1600\) cables.

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

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

Thus, \(1600 + 20 = 1620\) cables in total are needed.

Hence, the resultant answer is 1620 cables.