返回题库

HMMT 十一月 2017 · GEN 赛 · 第 8 题

HMMT November 2017 — GEN Round — Problem 8

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. Marisa has a collection of 2 − 1 = 255 distinct nonempty subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } . For each stepshe takes two subsets chosen uniformly at random from the collection, and replaces them with eithertheir union or their intersection, chosen randomly with equal probability. (The collection is allowed tocontain repeated sets.) She repeats this process 2 − 2 = 254 times until there is only one set left in 8
    the collection. What is the expected size of this set?
解析

英文解析

  1. Marisa has a collection of 2 − 1 = 255 distinct nonempty subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } . For each stepshe takes two subsets chosen uniformly at random from the collection, and replaces them with eithertheir union or their intersection, chosen randomly with equal probability. (The collection is allowed tocontain repeated sets.) She repeats this process 2 − 2 = 254 times until there is only one set left in 8
    the collection. What is the expected size of this set?
    Proposed by: Yuan Yao
    1024
    Answer:
    It suffices to compute the probability of each number appearing in the final subset. For any given 255
    7 7
    integer n ∈ [1 , 8], there are 2 = 128 subsets with n and 2 − 1 = 127 without. When we focus ononly this element, each operation is equivalent to taking two random sets and discarding one of themrandomly. Therefore there is a probability that n is in the final subset, and the expected value of 128
    128 1024255
    its size is 8 · = .
    255 255
    Alternatively, since | A | + | B | = | A ∪ B | + | A ∩ B | , the expected value of the average size of all remainingsubsets at a given step is constant, so the answer is simply the average size of all 255 subsets, which is
    8 · 128 1024 = .
    255 255