4

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 ?

Problem: You are given N boxes indexed from 1 to N. The number of boxes with 0, 1, or 2 coins is n0, n1, and n2, respectively. The number of empty boxes and the number of boxes with one coin are denoted by n0 and n1, n2 respectively. You take a random subset of the boxes where each subset has the same same probability to be selected. The empty set and the set itself are considered a subset.

What is the probability that the total number of coins in a random subset is divisible by 3.

Glen_b
  • 257,508
  • 32
  • 553
  • 939
Meliodas
  • 49
  • 1
  • 1
    "You take a random subset of the boxes where each subset has the same same probability to be selected" is an unusual sampling method. Could it be intended to mean that each *box* is equiprobable? Or does it really mean, according to a literal reading, that each of the $2^N$ possible subsets of the $N$ boxes is equally likely? Or could it mean something else? Regardless, please read the wiki at [tag:self-study] and edit your post to show how you interpret this question. – whuber Sep 19 '20 at 14:23
  • 1
    The exercice doesn't provide any other indication so to me, it means that each of the 2^ possible subsets of the boxes is equally likely – Meliodas Sep 19 '20 at 15:46
  • 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:58

1 Answers1

4

Understanding the question as literally meaning each of the $2^{n_0+n_1+n_2}$ subsets of boxes is equally likely, we may obtain a solution as follows.

A generating function for the counts of boxes of each type is

$$f(x_0,x_1,x_2;n_0,n_1,n_2) = (1+x_0)^{n_0}\,(1+x_1)^{n_1}\,(1+x_2)^{n_2}.$$

When expanded as a polynomial, the coefficient of $x_0^{k_0}x_1^{k_1}x_2^{k_2}$ counts the number of subsets of the boxes consisting of $k_0$ empty boxes, $k_1$ boxes with one coin, and $k_2$ boxes with two coins.

When $k_i$ boxes of type $i$ are chosen, the total number of coins is $k_1+2k_2.$ This total will be found as the coefficient of $x^{k_1+k_2}$ in the expansion of $$f(1,x,x^2;n_0,n_1,n_2) =2^{n_0}(1+x)^{n_1}(1+x^2)^{n_2}.$$ To find how many are multiples of $3$ we must decimate this expansion, giving the resulting count as

$$\begin{aligned} &F(n_0,n_1,n_2)=\\&(f(1,1,1;n_0,n_1,n_2) + \omega f(1,\bar\omega,(\bar \omega)^2;n_0,n_1,n_2) + \bar{\omega} f(1, \omega, \omega^2;n_0,n_1,n_2))/3 \end{aligned}$$

where $\omega^3=1$ is a primitive cube root of unity.

Writing $N=n_0+n_1+n_2,$ this simplifies to

$$F(n_0,n_1,n_2) = \left(2^N - 2^{n_0}q\right)/3$$

where the correction term, an integer in $\{-2,-1,1,2\},$ is

$$q = 2\cos\left(\frac{n_2-n_1+3}{3}\,\pi\right).$$

Multiply the count $F$ by the common chance of $2^{-N}$ to obtain the probability.

The value evidently will differ from $1/3$ by an exponentially small amount in $n_0-N=n_1+n_2.$

Here is a table of some of the probabilities.

Figure

The color bands highlight swathes of approximately equal numerators, where $n_1+n_2$ is constant. The patterns by which these numerators alternate are determined by the variation in the correction $q.$

whuber
  • 281,159
  • 54
  • 637
  • 1,101