Question

A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers.

Short answer

The resultant answer is that at least 2 computers are directly connected to the same number of other computers.

Step-by-step solution

Given data

There are 6 computers, is 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

Consider the 6 computers to be the pigeons and the number of possible direct connections to be the pigeonholes. As every computer is directly connected to at least one other computer, there are five pigeonholes, \(\{ 1\} ,\{ 2\} ,\{ 3\} ,\{ 4\} \), and \(\{ 5\} \).

Thus, by the pigeonhole principle, at least \(\left[ {\frac{6}{5}} \right] = 2\) computers are directly connected to the same number of other computers.

Hence, at least 2 computers are directly connected to the same number of other computers.