quiz8

1.1

Question

In a class of 200:

• 80 are funny
• 130 are clever
• 42 are neither funny nor clever How many are both funny and clever?

Answer

因此，答案为：52

1.2

Question

How many integers are there between 1 and 1000 which are divisible by 6 or 15 but not both?

Answer

• 集合A的大小，即1到1000之间可以被6整除的数的数量。（199）
• 集合B的大小，即1到1000之间可以被15整除的数的数量。（66）
• 集合A和B的交集的大小，即1到1000之间可以被30整除的数的数量。（33）

因此，答案为：166（因为33被计算了两次，所以199+66-33*2）

1.3

Question

Let S be a set of size n, and fix a constant k>1 (i.e k does not depend on n). Which of the following gives the best asymptotic upper bound for the number of subsets of S of size k?

Answer

集合不考虑顺序，因此只需要在n里选出k个元素，即 $(^n_k)$。

同时，由于k是常数，所以直接忽略。且：$(n-k)! \rightarrow O(n^k)$

因此，答案为：$O(n^k)$。

1.4

Question

Suppose I place 2 red balls, 3 green balls, and 4 blue balls into a hat, and draw two balls without replacement.

What is the probability they are both blue?

Answer

第一个球是蓝球的概率是4/9，满足第一次的情况下出现第二个蓝球的概率是4-1/9-1=3/8

因此，答案为：1/6

2.1

Question

How many ways are there of choosing an ordered sequence of three letters (with no replacements) from 'SYDNEY'?

Answer

计算三个字母的有序序列的总数，我们需要分四种情况来考虑：

• 序列中没有"Y"。
• 序列中有一个"Y"。
• 序列中有两个"Y"。

第一种情况，我们要从"SDNE"中选择三个，并组成有序序列，共有：$C_4^3 \times A^3_3 = 4 \times 6 = 24$。

第二种情况，我们要从"SDNE"中选择两个，并和另一个Y组成有序序列，共有：$C_4^2 \times A_3^3 = 6 \times 6 = 36$。

第三种情况，我们要从"SDNE"中选择一个，和另外两个"Y"组成有序序列。两个Y构成插槽，因此实际上该字母能选择位置只有3个，共有：$C_4^1 \times 3 = 12$。

因此，答案为：72

2.2

Question

How many sequences of 2n coin flips have exactly n heads and n tails?

Answer

我们只需要考虑，在这2n个硬币中，选择n个正面朝上即可，我们不需要考虑它的顺序或者别的东西。

因此，答案为：$(^{2n}_n)$

2.3

Question

How many ways are there of placing 6 indistinguishable balls into 3 distinguishable boxes so that each box contains at least 1 ball?

Answer

六个球是等价的，三个盒子不等价。我们可以先在每个盒子中都放一个球，把问题转化为：

现在有3个球，放入三个不同的盒子中，有几种放法？

有三种情况：

1. 三个球在一个盒子里（3种）
2. 有一个盒子是空的，另外两个盒子2&1分布（3*2）
3. 三个球在三个盒子里（1种）

因此，答案为：10

2.4

Question

Suppose I place 2 red balls, 3 green balls, and 4 blue balls into a hat, and draw two balls without replacement.

What is the probability that the second ball is blue, given that the first ball is blue?

Answer

感觉跟前面那题没区别，答案为3/8