# Count subset divisible by 3

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 $$n_0$$, $$n_1$$, and $$n_2$$, 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?

• We discourage posts that are just the statement of an exercise-style task and a request for us to show you the solution to the exercise. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. If you're stuck, you can try adjusting the problem to make it easier, e.g., by assuming each box has 0 or 1 coins, or making N small. Can you spend some time on this, and then show us what progress you've made so far? – D.W. Sep 19 '20 at 19:57
• What's the original source where you encountered it? What is the context? What concepts are you learning right now? Providing context increases the likelihood you will get a good answer. – D.W. Sep 19 '20 at 19:57
• – D.W. Oct 3 '20 at 5:55

You can use generating functions. Let me switch notations to $$a = n_1$$ and $$b = n_2$$, noticing that empty boxes make no difference. The generating function for the total number of coins is $$\left(\frac{1+x}{2}\right)^a \left(\frac{1+x^2}{2}\right)^b,$$ that is, the coefficient of $$x^m$$ is the probability that the boxes contain a total of $$m$$ coins. The trick is now to substitute cubic roots of $$3$$ for $$x$$, using the following observation, where $$\omega = e^{2\pi i/3}$$: $$\frac{1^m + \omega^m + (\omega^2)^m}{3} = \begin{cases} 1 & \text{if } 3 \mid m, \\ 0 & \text{otherwise}. \end{cases}$$ Using this, we find that the probability that you're after is $$\frac{1}{3} + \frac{1}{3} \left(\frac{1+\omega}{2}\right)^a \left(\frac{1+\omega^2}{2}\right)^b + \frac{1}{3} \left(\frac{1+\omega^2}{2}\right)^a \left(\frac{1+\omega}{2}\right)^b.$$

This formula is not necessarily so helpful. Instead, we can use dynamic programming, which can be succinctly expressed using matrices. Suppose that we open the boxes one by one (each one with probability $$1/2$$), and keep track of the vector of probabilities of the various residues modulo $$3$$, a column vectors whose entries correspond to the residues $$0,1,2$$. An opened box with one coin affects the vector according to the matrix (multiplying the vector on the left) $$\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}.$$ If instead we open the box with probability $$1/2$$, we get the average of this matrix with the identity matrix: $$\begin{pmatrix} \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \end{pmatrix}.$$ We can analyze boxes with two coins similarly, and over all the vector of probabilities is $$\begin{pmatrix} \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \end{pmatrix}^a \begin{pmatrix} \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & \tfrac{1}{2} \end{pmatrix}^b \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}$$ You can get your probability by taking the first entry. The matrix expression above can be evaluated in many ways – by multiplying the vector matrix-by-matrix, using repeated squaring to compute the matrix powers, or by diagonalizing the matrices to obtain an even more rapid algorithm (which is identical to the formula obtained above using generating functions).

Finally, let me spell out the dynamic programming algorithm, which just implements the matrix-by-matrix approach hinted to above:

• Initially, $$(p_0,p_1,p_2) \gets (1,0,0)$$.
• Repeat $$n_1$$ times: $$(p_0,p_1,p_2) \gets (\frac{p_0+p_2}{2},\frac{p_0+p_1}{2},\frac{p_1+p_2}{2})$$.
• Repeat $$n_2$$ times: $$(p_0,p_1,p_2) \gets (\frac{p_0+p_1}{2},\frac{p_1+p_2}{2},\frac{p_0+p_2}{2})$$.
• Thank you so for this answer. To provide some context, it is an interview exercice that I was trying to solve. No need to say that I won't try to go any further in the process but I just wanna train and improve myself. I think clearly the DP approach was the one expected but I don't understand why you said that we open box one by one with probability 1/2. The probability should be n0/n to pick a box of 0 coin, n1/n to pick a box of 1 coin etc... I feel like I'm missing something – Meliodas Sep 20 '20 at 9:29
• What I am missing is a clear explanation of the problem. It's not clear what the following means: You take a random subset of the boxes where each subset has the same same probability to be selected. I interpreted it to mean that we choose a random subset of the $n_0+n_1+n_2$ boxes, that is, we consider all $2^{n_0+n_1+n_2}$ subsets, and choose one uniformly at random. This is the same as choosing each box with probability $1/2$, independently. – Yuval Filmus Sep 20 '20 at 9:32
• I posted the problem as I received it. There was no more additional information so I suppose your interpretation is the correct one. – Meliodas Sep 20 '20 at 9:35
• Also, the sentence "The number of empty boxes and the number of boxes with one coin are denoted by n0 and n1, n2 respectively." in the problem statement seems spurious. Have you copied the problem correctly? – Yuval Filmus Sep 20 '20 at 9:36
• I corrected this one it was a bad insert that I made while copying the problem. – Meliodas Sep 20 '20 at 9:46