Can you solve this IT puzzle?

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.

16 28 32 20

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.

4 solutions

Ivan Koswara
Aug 31, 2015

First, I claim that 20 20 cables work.

Number the computers 1 , 2 , , 8 1, 2, \ldots, 8 and the printers 1 , 2 , 3 , 4 1, 2, 3, 4 . Connect computer i i to printer i i for all i { 1 , 2 , 3 , 4 } i \in \{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 19 19 cables doesn't work.

By Pigeonhole Principle, with 19 19 cables and 4 4 printers, one printer is connected to at most 4 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.

Moderator note:

Good usage of the pigeonhole principle here to explain why 19 cables isn't sufficient. Sometimes, it helps to consider different perspectives of applying PP (on the computers, or on the printers).

nice one bro.

Chandrakant Pandey - 5 years, 9 months ago
Richard Zhou
Aug 31, 2015

The problem actually becomes a lot simpler if you consider it from the perspective of the printers, rather than the computers: each printer needs to be connected to some subset of the computers such that for any combination of four computers, each printer is connected to at least one of them.

Each printer then needs to be connected to at least five of the eight computers: so a total of 5*4 = 20 \boxed{20} cables are needed.

This comment is incorrect.


I disagree with "Each printer then needs to be connected to at least five of the eight computers"

For example, we could have five computers connected to all printers, and then the remaining three computers connected to none of the printers.

Calvin Lin Staff - 5 years, 9 months ago

Log in to reply

Correct me if I'm wrong, but if five computers are connected to all the printers, wouldn't each of those printers would be connected to five computers? My solution approaches the problem from the perspective of the printers, not the computers.

Richard Zhou - 5 years, 9 months ago

Log in to reply

Oh, my bad. I don't even know what I was saying.

What you wrote makes perfect sense.

Calvin Lin Staff - 5 years, 9 months ago
Matin Naseri
Jan 22, 2018

n!-n \text{n!-n} .

4!=24 \text{4!=24} .

24-4=20 \text{24-4=20} .

Hence the answer is 20 \boxed{20} .

Yash Shah
Sep 6, 2015

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...