0

I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size k but it didn't helped me that much. Is anyone kind enough to give me the right approach to solve this ?

There are N boxes indexed from 1 to N. Each box contains either no coins or one coin. The number of empty boxes and the number of boxes with one coin are denoted by n0 and n1, respectively. You take a random subset of the boxes where each subset has the same probability to be selected. The empty set and the set itself are considered a subset. Given n0 and n1, what is the probability that the total number of coins in the random subset is even?

whuber
  • 281,159
  • 54
  • 637
  • 1,101
Shiv948
  • 111
  • 1
    See https://stats.stackexchange.com/questions/488210/probability-problem-probability-to-pick-a-subset-divisible-by-3/488222#488222 for an approach to a more complicated version of this problem. Your problem is much simpler, though, because it's only a question of whether the subset contains an even number of boxes with one coin. So, first solve the problem with $n_0=0$ and then consider how the answer changes as you increase $n_0.$ – whuber Sep 26 '20 at 16:34
  • 1
    Here's another hint: assume there is at least one coin. (You can deal with the alternative easily!) Mark that coin. There are two kinds of subsets: those that include it and those that do not. Indeed, the coin induces a one-to-one correspondence between those collections of subsets: any subset with the coin is associated with the subset with that coin missing. Exploit this correspondence to write down the answer with no further calculation. – whuber Sep 26 '20 at 18:41
  • 1
    Cross-posted: https://cs.stackexchange.com/q/130312/755, https://stats.stackexchange.com/q/489249/2921, https://stats.stackexchange.com/q/488210/2921. Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). – D.W. Oct 03 '20 at 05:55

0 Answers0