2
$\begingroup$

A system administrator has to connect 16 computers to 4 network switches. Exactly 3 computers must be connected to the first network switch.

  1. Show that there must exist a switch that has at least 5 connected computers.
  2. In how many ways can we connect the computers if we know that they are all different?
  3. In how many ways can we connect the computers if we know that they are all the same?

I tried solving the third question with first finding the $3$-combinations for all $16$ computers: $\binom{16+3-1}{16} = 153$ ways and then for the remaining $3$ switches I used the equation: $x_1+x_2+x_3=13$, with $x_1$ having at least $5$ connected computers, meaning $x_1>4$. The solution I got was $84$ ways. $153+84$ ways $= 237$ ways.

I don't know if this is the right approach. I would like to know if I am on the right path and what am I doing wrong.

$\endgroup$
4
  • $\begingroup$ Please edit your question to show what you have attempted and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Jan 12 '20 at 17:45
  • $\begingroup$ Welcome to MSE. You'll get a lot more help, and fewer votes to close, if you show that you have made a real effort to solve the problem yourself. What are your thoughts? What have you tried? How far did you get? Where are you stuck? This question is likely to be closed if you don't add more context. Please respond by editing the question body. Many people browsing questions will vote to close without reading the comments. $\endgroup$ – saulspatz Jan 12 '20 at 17:47
  • $\begingroup$ Did you mean all $16$ computers? Also, can a computer be connected to more than one switch? $\endgroup$ – N. F. Taussig Jan 12 '20 at 21:17
  • $\begingroup$ Yes I mean 16, not 24. I edited my mistake. Also, a computer can be connected to only one switch. $\endgroup$ – lina Jan 12 '20 at 21:42
1
$\begingroup$

We are told that exactly three computers are connected to the first network switch. That means $16 - 3 = 13$ computers are connected to the remaining three network switches. If we let $x_i$ be the number of computers connected to the $i$th network switch, then $$x_2 + x_3 + x_4 = 13$$ which is an equation in the nonnegative integers. A particular solution of the equation corresponds to the placement of $3 - 1 = 2$ addition signs in a row of $13$ ones. For instance, $$1 1 + 1 1 1 1 1 1 + 1 1 1 1 1$$ corresponds to the solution $x_2 = 2$, $x_3 = 6$, $x_4 = 5$. The number of such solutions is $$\binom{13 + 3 - 1}{3 - 1} = \binom{15}{2} = 105$$ since we must choose which two of the $15$ positions required for $13$ ones and two addition signs will be filled with addition signs. Thus, there are $105$ ways to connect $16$ identical computers to the four network switches if exactly three of those computers are connected to the first network switch.

It looks like you were misled by the wording of the first part of the question. If exactly three computers are connected to the first switch, then $13$ computers must be connected to the remaining network switches. At least one of those three switches must be connected to at least five computers, otherwise there would only be at most $3 + 4 + 4 + 4 = 15$ computers connected to the network switches, a contradiction. Since exactly three computers must be connected to the first network switch, the case in which $x_1 > 4$ is ruled out.

$\endgroup$
2
  • $\begingroup$ I understand your logic, thank you. But, how can we solve it if the computers are all different? $\endgroup$ – lina Jan 13 '20 at 13:05
  • $\begingroup$ If the computers are all different, choose which three of them are connected to the first network switch. Each of the remaining $13$ computers must be connected to one of the other three switches. Thus, there are $\binom{16}{3}3^{13}$ ways to connect the computers to the network switches if all the computers are different and exactly three of them must be connected to the first network switch. $\endgroup$ – N. F. Taussig Jan 13 '20 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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