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.

  • 1
    $\begingroup$ "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 self-study and edit your post to show how you interpret this question. $\endgroup$ – whuber Sep 19 '20 at 14:23
  • 1
    $\begingroup$ 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 $\endgroup$ – Meliodas Sep 19 '20 at 15:46
  • 1

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.


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.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.