Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite
1

Five microcomputers are to be connected to three printers.How many connections are necessary between computers and printers in order to ensure that whenever any three computers require a printer the printers are available?

share|improve this question
3  
What are your thoughts about this? – Rasmus Oct 10 '10 at 17:28
2  
This looks like homework. You should tell us what you've done so far and where you're stuck. – Qiaochu Yuan Oct 10 '10 at 17:41
1  
@Qiaochu: scolding under each post is not efficient or scalable. Isn't it better to develop generic tools (tags, ratings, filtering mechanisms, FAQs, specialized sub-sites) that apply to all postings? – T.. Nov 9 '10 at 6:18
they just need to be connected somehow: 5+3=8 devices, that need not more than 8-1=7 connections. do you want to specify any extra conditions? – comonad Nov 9 '10 at 8:38
You should define whether three computers simultaneously want a printer and you have enough connections to satisfy them when you know which three they are, or whether they sequentially request a printer and you have to assign them upon request. The second case takes more connections. Weltschmerz' solution fails in the second. If C4 and C5 make the first two requests, the third request may not come from the right one of C1, C2, and C3 to be satisfied. – Ross Millikan Nov 10 '10 at 1:03

2 Answers

up vote 1 down vote

mcAfee, here's a hint: call P1, P2, P3 the printers and C1, ..., C5 the computers. Suppose P1 is connected to C1, C4, C5; P2 is connected to C2, C4, C5, and P3 is connected to C3, C4, C5. That is 9 connections (and this is not the only way to connect them; you should try others). Check out whether this works, and if it does, try and see whether it's possible to do it with 8 connections.

share|improve this answer
up vote 1 down vote

To connect all computers to each other you need n-1 connections, i.e., 4. To connect 3 printers you need exactly 3 connections. So the number connections required is 7.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.