COMP 1002 Winter 2019
Homework Assignment # 6
Due: April 1, by 10pm
(Type it up and upload on D2L)

In all problems, as usual in this course, show how you got the answer, in particular which formulas, rules and definitions you used, and why. Just writing a number is not enough for the full mark.

1. Combinations and permutations [45]

A datacenter has 10 servers and 4 routers, which they want to connect. Each server and each router can have any number of cables attached to it.

1. How many cables would they need to connect each server to each router directly?

Solution:

2. Suppose they connect each server to only one router. How many different ways are there to run the connections, assuming that each router has at least one server connecting to it? Here, assume every server and every router has a different name, and you need to find out how many ways to connect names of servers with names of routers.

Solution:

3. They need to order 10 cables to connect servers to routers. The cables come in 1ft, 2ft and 4 ft lengths. How many different orders can be placed, ranging from all 1ft cables to all 4ft with all the intermediate combinations 1ft, 2ft and 4ft cables?

Solution:

4. Now they want to arrange all servers and routers on two racks, each of which has 7 shelves. They want to have two routers on each rack, and want routers to be not on the ends of the racks and not next to each other. How many ways are there to put router shelves into those two racks? (Here, having router shelves 2 and 4 on rack 1 and 3 and 6 on rack 2 is different from having router shelves 3 and 6 on rack 1, with 2 and 4 on rack 2).

Solution:

2. Combinatorial identities [15]

Prove that for every $n \in \mathbb{N}$, $\binom{2n}{2} = 2\binom{n}{2} + n^2$. Hint: you don't need to use induction, just the definition of $\binom{n}{k}$, universal instantiation/generalization and some calculations.

Solution:

3. Probabilities and Bayes theorem [40]

1. According to Statistics Canada, roughly $26\%$ of people in NL get a flu shot, which is 72% effective in 2018-19 (if probability of going to a doctor with severe flu is $p$ for unvaccinated people, and effectiveness is $x\%$, then it is $p(1-x/100)$ for vaccinated). This year, there were 516 confirmed severe flu cases in NL (out of population of 525,355). Based on this information, how many people in NL did not go to the doctor this year with a severe flu thanks to a flu shot?

Solution:

2. Suppose that 10\% of the patients with a flu tested in a hospital are infected with flu strain H3N2. Furthermore, suppose that in a blood test for H3N2, 95\% of the patients infected with H3N2 test positive and that 4\% of the patients not infected with H3N2 test positive. Calculate probability that a person with a flu has the H3N2 flu strain given that the test came back negative (that is, the probability of a false negative).

Solution:

4. Bonus [20]

Suppose that in the datacenter problem above they would like the connections to satisfy the following property: at any given time, if no more than 4 servers are transmitting data, then each server can transmit via a separate router. For that, they want every (sub)set of 4 to have cables going to all four routers. What is the minimal number of cables needed to achieve this, and how the servers and routers should be connected in this case? Prove both that your scheme satisfies the condition that every set of 4 servers has cables to all routers, and that the number of cables you used is indeed minimal (hint: use the PigeonHole Principle to prove minimality).

Solution: