返回题库

集齐整套

Complete Sets

专题
Probability / 概率
难度
L4

题目详情

有 5 个不同的组，每个组有 3 个块。随机移除六个块。计算剩余的完整组的预期数量。

There are 5 distinct sets with 3 blocks each. Six blocks are removed at random. Compute the expected number of complete sets remaining.

解析

让我们看看是否有任何给定的集合保持完好。为了使集合保持完整，只能删除不同集合的块。因此，任何给定集合保持完整的概率为： 1215⋅1114⋅1013⋅912⋅811⋅710=1265\frac{12}{15} \cdot \frac{11}{14} \cdot \frac{10}{13} \cdot \frac{9}{12} \cdot \frac{8}{11} \cdot \frac{7}{10} = \frac{12}{65} 由于块是随机删除的，因此没有一组或多或少可能保持完整。根据期望的线性度，完整集合的期望数量为： 5⋅1265=12135 \cdot \frac{12}{65} = \boxed{\frac{12}{13}}

import random

complete_set_counts = []
num_iters = 100_000
for i in range(num_iters):

    sets = ['A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'D', 'E', 'E', 'E']

    #removing 6 random elements
    for j in range(6):
        sets.pop(random.randrange(0, len(sets)))

    complete_set_count = 0
    #iterating over ascii values for chars A-E
    for j in range(65, 70):
        if sets.count(chr(j)) == 3:
            complete_set_count += 1

    complete_set_counts.append(complete_set_count)

#expecting ~ 0.923
print(sum(complete_set_counts)/num_iters)

Original Explanation

Let's take a look at if any given set remains intact. For a set to remain complete, only blocks of different sets can be removed. Thus the probability any given set remains intact is: 1215⋅1114⋅1013⋅912⋅811⋅710=1265\frac{12}{15} \cdot \frac{11}{14} \cdot \frac{10}{13} \cdot \frac{9}{12} \cdot \frac{8}{11} \cdot \frac{7}{10} = \frac{12}{65}

Since blocks are removed at random, no set is more or less likely to remain complete. By linearity of expectation, the expected number of complete sets is: 5⋅1265=12135 \cdot \frac{12}{65} = \boxed{\frac{12}{13}}

import random

complete_set_counts = []
num_iters = 100_000
for i in range(num_iters):

    sets = ['A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'D', 'E', 'E', 'E']

    #removing 6 random elements
    for j in range(6):
        sets.pop(random.randrange(0, len(sets)))

    complete_set_count = 0
    #iterating over ascii values for chars A-E
    for j in range(65, 70):
        if sets.count(chr(j)) == 3:
            complete_set_count += 1

    complete_set_counts.append(complete_set_count)

#expecting ~ 0.923
print(sum(complete_set_counts)/num_iters)