1. Homer's Pizza is advertising the following deal:

• 3 pizzas, up to 4 toppings each, 10 toppings to choose from • 3 soft drinks, 5 varieties to choose from

• total cost $24.99

The pizza toppings must be unique-double, triple, or quadruple toppings are not allowed. The order of the toppings is not relevant, and 3 of the same pizza and/or 3 of the same soft drink is allowed.

Homer's Pizza is setting up an advertising campaign and would like to brag about the total number of combinations to choose from. Let's help them get this right. What is the total number of combinations of pizzas + soft drinks possible with this offer? Show all of your work-intermediate formulae and final answer.

2. How many integer solutions are there to the equation
x1 + x2 + 2x3 + x4 + x5 = 72
when

(a) xi 0,i = 1,...,5
(b) xi 1,i = 1,...,5

3. Consider the Fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .

The n-th number in this sequence is the sum of the (n 1)-st and (n 2)-nd number, or, more
formally, the Fibonacci sequence Fn, n = 0, 1, . . . is defined as:

F0 =0; F1 =1; Fn =Fn1 +Fn2, n2.

(In lecture we hinted that (1) is embedded in Pascal's triangle by investigating "stretched diagonals". While this is true, it is not obvious how the sequence is embedded.

Redraw Pascal's triangle to make it clear how the Fibonacci sequence is embedded in the triangle, and explain the calculation required to obtain the sequence. A formal proof is not required; an observation over 12 rows of the triangle will suffice. You may use the fact that the r-th number in the n-th row of the triangle is C(n, r) when explaining the calculation.

Hint: Pascal's triangle does not need to be drawn as an isosceles triangle.)

4. An urn contains seven red balls, seven white balls, and seven blue balls. A sample of five balls is
drawn at random without replacement. Compute the probability that:

(a) The sample contains four balls of one colour and one ball of another colour. (b) All of the balls are of the same colour.

(c) The sample contains at least one ball of each colour.

5. Consider the Birthday Problem discussed in lecture. In this problem we calculate the probability that, in a group of n people, at least two have the same birthday.

Let E be the event that at least two people share a birthday. In order to calculate P (E), we first need a sample space. A possible sample space consists of n-tuples of the integers 1 . . . 365 (each of n people have a birthday on one of the 365 days of the year; leap years are not considered).

(a) List or otherwise describe the sample space for n = 200. What is the size of the sample space?

(b) For n = 200, write an algorithm (in pseudo-code or in Python) for enumerating the number of tuples in the sample space that satisfy the condition that at least two people have the same birthday. (Note that your algorithm will need to scan each tuple.)

(c) Say you have access to one of the fastest computers currently available ...China's Tianhe-2 benchmarked at 33.86-petaflops (33.86 ? 1015 floating point operations per second), and say that a scan of a single tuple in your algorithm uses 1 floating point operation. (You will learn about floating point operations in a later course; for now, rest assured this is an underestimate for the cost required to scan a tuple.) How many seconds will your algorithm use to process all of the tuples in the sample space?

(d) For n = 200, state the running time of your algorithm in years. Do some research on Google and state the running time of your algorithm in measures of millennia, epochs, eras, and eons (time spans in geochronology), and in terms of the age of the (i.e., our) universe.

6. The results of the previous question should make it clear that solving the birthday problem by scanning the sample space is not computationally feasible for n = 200. In fact, scanning the sample space is not computationally feasible for n much smaller than 200.

Fortunately, as we saw in lecture, the problem can be solved easily by first computing the complement probability P (E ) . . . the probability that everyone has a distinct birthday. Then P (E ) = 1 P (E ).

For n = 3, the sample space of approximately 49 million tuples is small enough that it could be scanned. However, for n = 3 the problem could also be solved directly with counting principles. Calculate P (E ) for n = 3 using counting principles, and confirm that it is the same as 1 P (E ).

7. A ternary string is a string consisting of 0s, 1s, and 2s. Suppose we are transmitting ternary strings through a noisy communication channel with the following known probabilities:

• 0 is sent with probability 0.3
• 1 is sent with probability 0.4
• 2 is sent with probability 0.3
• Due to noise, 0 is changed to 1 during transmission with probability 0.2
• Due to noise, 0 is changed to 2 during transmission with probability 0.1
• Due to noise, 1 is changed to 0 during transmission with probability 0.2
• Due to noise, 1 is changed to 2 during transmission with probability 0.1
• Due to noise, 2 is changed to 0 during transmission with probability 0.2
• Due to noise, 2 is changed to 1 during transmission with probability 0.1

Suppose that a 1 is received. What is the probability that a 1 was sent? You must use both Bayes' Formula and the theorem of Total Probability to answer this question. Show all of your work.