Evaluation: 2015 Winter Final

Author: Michiel Smid

1 . Consider a set

S

consisting of 20 integers; 5 of these are even and the other 15 integers in

S

are odd. What is the number of 7-element subsets of

S

having exactly 3 even integers?

(a)

(\binom{20}{7})

(b)

(\binom{5}{3}) + (\binom{15}{4})

(c)

(\binom{5}{4}) (\binom{15}{3})

(d)

(\binom{5}{3}) (\binom{15}{4})

2 . Consider a set

S

consisting of 20 integers; 5 of them are even and the other 15 integers in

S

are odd. What is the number of 7-element subsets of

S

having at least 5 even integers or at least 5 odd integers?

(a)

(\binom{5}{5}) (\binom{15}{2}) + (\binom{5}{2}) (\binom{15}{5}) + (\binom{5}{1}) (\binom{15}{6}) + (\binom{5}{0}) (\binom{15}{7})

(b)

None of the above.

(c)

(\binom{5}{5}) (\binom{15}{2}) + (\binom{5}{2}) (\binom{15}{5}) - (\binom{5}{5}) (\binom{15}{5})

(d)

(\binom{20}{7}) - (\binom{5}{4}) (\binom{15}{4})

3 . How many bitstrings of length 77 start with 1111 or end with 0000?

(a)

2^{74} - 2^{69}

(b)

2^{77} - 2^{69}

(c)

2^{77} - 2^{73} - 2^{73}

(d)

2^{73} + 2^{73}

4 . What is the coefficient of

x^{4} y^{11}

in the expansion of

(2 x - 7 y)^{15}

(a)

- (\binom{15}{11}) \cdot 2^{11} \cdot 7^{4}

(b)

(\binom{15}{11}) \cdot 2^{11} \cdot 7^{4}

(c)

(\binom{15}{11}) \cdot 2^{4} \cdot 7^{11}

(d)

- (\binom{15}{11}) \cdot 2^{4} \cdot 7^{11}

5 . In a group of 20 people,

6 are blond,
7 have green eyes,
11 are not blond and do not have green eyes.

How many people in this group are blond and have green eyes?

(a)

(b)

(c)

(d)

6 . Let

n \geq 7

be an integer. Why does the following equality hold:

(\binom{n}{5}) (\binom{n - 5}{2}) = (\binom{n}{2}) (\binom{n - 2}{5})

(a)

Because both sides count the number of ways to choose 2 committees in a group of

n

people, one committee has 5 members, the other committee has 2 members, and <strong>no</strong> person can be on both committees.

(b)

Because both sides count the number of pairs

(A, B)

of subsets of the

n

people, such that

| A | = 5

| B | = 2

, and

A \subseteq B

(c)

Because both sides count the number of ways to choose 2 committees in a group of

n

people, one committee has 5 members, the other committee has 2 members, and a person can be on both committees.

(d)

Because both sides count the number of pairs

(A, B)

of subsets of the

n

people, such that

| A | = 2

| B | = 5

, and

A \subseteq B

7 . Consider strings of characters, each character being

a

b

, or

c

, that contain an odd number of

a

s. Let

S_{n}

be the number of such strings having length

n

. Which of the following is true?

(a)

S_{n} = 2 \cdot S_{n - 1} + S_{n - 2}

(b)

S_{n} = S_{n - 1} + S_{n - 2}

(c)

S_{n} = S_{n - 1} + (3^{n - 1} - S_{n - 1})

(d)

S_{n} = 2 \cdot S_{n - 1} + (3^{n - 1} - S_{n - 1})

8 . Consider the following recursive function:

f(0) = $7$ ,
f(n) = $f (n - 1) + 6 n - 3 for all$ $integers n \geq 1$ .

Which of the following is true??

(a)

For all

n \geq 0

f (n) = 3 n^{2} + 7

(b)

None of the above.

(c)

For all

n \geq 0

f (n) = 4 n^{2} + 7

(d)

For all

n \geq 0

f (n) = 2 n^{2} + 7

9 . Consider the recursive algorithm

F I B

, which takes as input an integer

n \geq 0

$Algorithm F I B (n) :$
$if n = 0 or n = 1$
$then f = n$
$else f = F I B (n - 1) + F I B (n - 2)$
$endif;$
$return f$

If we run algorithm

F I B (77)

, how many calls are there to

F I B (73)

(a)

(b)

(c)

(d)

10 . Let

S

be the set of ordered pairs of integers that is recursively defined in the following way:

$(1, 6) \in S$ .
If $(a, b) \in S$ then $(a + 3, b + 4) \in S$ .
If $(a, b) \in S$ then $(a + 5, b + 2) \in S$ .

Which of the following is true?

(a)

For every element

(a, b)

S

a + b

is not divisible by 7.

(b)

None of the above.

(c)

S = {(a, b) : a > 0

and

b > 0

are integers and

a + b

is divisible by 7

}

(d)

For every element

(a, b)

S

a + b

is divisible by 7.

11 . How many solutions are there to the equation

x_{1} + x_{2} + x_{3} + x_{4} = 99

, where

x_{1} \geq 0

x_{2} \geq 0

x_{3} \geq 0

x_{4} \geq 0

are integers?

(a)

(\binom{102}{4})

(b)

(\binom{103}{3})

(c)

(\binom{103}{4})

(d)

(\binom{102}{3})

12 . Consider two events

A

and

B

in a sample space

S

. You are given that

Pr (B) = 2 / 3

and

Pr (A | B) = 4 / 5

. What is

Pr (A \cap B)

(a)

6/15

(b)

5/15

(c)

7/15

(d)

8/15

13 . Consider three events,

A

B

, and

C

in a sample space

S

. Is the following true or false?

Pr (A \cup (\overset{―}{B} \cap \overset{―}{C})) =

Pr (A) + Pr (B) -

Pr (C) .

(a)

None of the above.

(b)

True

(c)

False

14 . Let

S

be a set of 100 integers; 30 of these are positive and the other 70 integers in

S

are negative. We choose, uniformly at random, a 20-element subset of

S

. What is the probability that at least one of the elements in this subset is positive?

(a)

None of the above.

(b)

(\binom{30}{1}) (\binom{70}{19}) / (\binom{100}{20})

(c)

1 - (\binom{70}{20}) / (\binom{100}{20})

(d)

(\binom{30}{1}) / (\binom{100}{20})

15 . Let

S

be a set of 100 integers; 30 of these are positive and the other 70 integers in

S

are negative. We choose, uniformly at random, a 20-element subset of

S

. Let

x

be the product of the integers in the chosen subset. What is the probability that

x > 0

(a)

\frac{1}{(\binom{100}{20})} \sum_{k = 0}^{10} ((\binom{70}{2 k}) + (\binom{30}{20 - 2 k}))

(b)

\frac{1}{(\binom{100}{20})} \sum_{k = 0}^{10} (\binom{70}{2 k}) (\binom{30}{20 - 2 k})

(c)

\frac{1}{(\binom{100}{20})} \sum_{k = 0}^{20} ((\binom{70}{k}) + (\binom{30}{20 - k}))

(d)

\frac{1}{(\binom{100}{20})} \sum_{k = 0}^{20} (\binom{70}{k}) (\binom{30}{20 - k})

16 . Consider a bitstring of length 77, in which each bit is 0 with probability 1/3 (and, thus, 1 with probability 2/3), independently of the other bits. What is the probability that there are exactly 15 0s in this bitstring?

(a)

(\binom{77}{15}) ((1 / 3)^{62} + (2 / 3)^{15})

(b)

(\binom{77}{15}) ((1 / 3)^{15} + (2 / 3)^{62})

(c)

(\binom{77}{15}) (1 / 3)^{15} (2 / 3)^{62}

(d)

(\binom{77}{15}) (1 / 3)^{62} (2 / 3)^{15}

17 . Consider a uniformly random bitstring of length 5. Define the events

A = "the bitstring contains exactly two 0s",
B = "the bitstring contains an even number of 0s".

(Note that zero is even.) What is the conditional probability

Pr (A | B)

(a)

2^{5} / (\binom{5}{2})

(b)

(\binom{5}{2}) / 2^{3}

(c)

(\binom{5}{2}) / 2^{4}

(d)

(\binom{5}{2}) / 2^{5}

18 . Consider a uniformly random bitstring of length 5. Define the events

A = "the bitstring contains an odd number of 0s"

and

B = "the first three bits in the bitstring are 111".

Which of the following is true?

(a)

None of the above.

(b)

The events

A

and

B

are not independent.

(c)

The events

A

and

B

are independent.

19 . I flip a fair coin, independently,

n

times. For each heads, you win $3, whereas for each tails, you lose $1. Define the random variable

X

to be the amount of dollars that you win. What is the expected value of

X

(a)

n

(b)

3 n / 2

(c)

n / 2

(d)

2 n

20 . Let

G = (V, E)

be a graph with vertex set

V

and edge set

E

, let

n

be the size of

V

, and let

m

be the size of

E

. For each vertex of

V

, flip a fair and independent coin. Let

V^{'}

be the subset of

V

consisting of all vertices of

V

whose coin flip resulted in heads. Let

E^{'}

be the set consisting of all edges

(u, v)

E

for which both

u

and

v

are in

V^{'}

. Define the random variable

X

to be the number of edges in

E^{'}

. What is the expected value of

X

(a)

m / 16

(b)

m / 2

(c)

m / 4

(d)

m / 8

21 . Consider a bitstring of length 5, in which each bit is 0 with probability 1/2 (and, thus, 1 with probability 1/2), independently of the other bits. Define the random variables

X

and

Y

as follows:

X = the number of 0s in this bitstring

and

Y = the value of the first bit in this bitstring.

Which of the following is true?

(a)

None of the above.

(b)

The random variables

X

and

Y

are not independent.

(c)

The random variables

X

and

Y

are independent.

22 . One of Lindsay and Simon is chosen uniformly at random. The person that is chosen wins $100. Define the random variables

L

and

S

as follows:

L = the amount that Lindsay wins

and

S = the amount that Simon wins.

Which of the following is true?

(a)

E (L) = 100

and

E (max (L, S)) = 100

(b)

E (L) = 100

and

E (max (L, S)) = 50

(c)

E (L) = 50

and

E (max (L, S)) = 50

(d)

E (L) = 50

and

E (max (L, S)) = 100

23 . Consider the following recursive algorithm

T W O T A I L S

, which takes as input a positive integer

k

Algorithm T W O T A I L S (k) :

/ /

all coin flips made are mutually

independent

flip a fair coin twice;

if the coin came up heads exactly twice

then return 2^{k}

else T W O T A I L S (k + 1)

endif

You run algorithm

T W O T A I L S (1)

, i.e., with

k = 1

. Define the random variable

X

to be the value of the output of this algorithm. Let

k \geq 1

be an integer. What is

Pr (X = 2^{k})

(a)

(1 / 4)^{k} \cdot 3 / 4

(b)

(3 / 4)^{k} \cdot 1 / 4

(c)

(1 / 4)^{k - 1} \cdot 3 / 4

(d)

(3 / 4)^{k - 1} \cdot 1 / 4

24 . You repeatedly, and independently, roll two fair dice, until the sum of the values of the two dice is equal to 12. Define the random variable

X

to be the number of times you roll the pair of dice. What is the expected value of

X

(a)

(b)

(c)

(d)

25 . Who is Lindsay Bangs?

(a)

Goalie of the Ottawa Senators, her nickname is The Hamburglar.

(b)

A world-renowned rapper.

(c)

Owner of the brewery that produces Leo's Early Breakfast IPA.

(d)

President of the Carleton Computer Science Society.