Find the number of $n$ digit positive integers divisible by 3 whose digits are from the set $\{2,3,7,9\}$ (with or without repetition)

Question

The solution goes like this

Number of ways to fill first seat is $x^2+x^3+x^7+x^9$

This is same for all seats

So number of ways to fill $n$ seats is

$$(x^2+x^3+x^7+x^9)^n$$

The summation of powers must be divisible by 3. So we want coefficient of $x^{3k}$ in $(x^2+x^3+x^7+x^9)^n$

So let $x=1,\omega , \omega^2$ where $\omega, \omega^2$ are cube roots of unity.

$$A=(1+1+1+1)^n =4^n$$ $$A=(\omega ^2 + 1 + \omega + 1)^n=1$$ $$A=(\omega +1+\omega + 1)^n=1$$

So $$A=\frac{4^n+2}{3}$$

I have no idea why and how they wrote it all in terms of $x$. I dont know what $x$ represents. Is this an algorithm or something conceptual?

Answer 1

As another way to do the computation:

Let $A_n$ be the number of "good" strings of length $n$. Let $B_n$ be the number of bad strings of length $n$, so $B_n=4^n-A_n$.

We remark that, for any bad string, there is a unique choice in the list that you can append to get a good string. For a good string, however, there are exactly two choices. Considering the sum of the digits therefore shows that we have the recursion $$A_{n+1}=2A_n+B_n$$

And, since $B_n=4^n-A_n$, this implies $$A_{n+1}=4^n+A_n$$ which quickly implies your formula.

Answer 2

Here the solution exploits the property of exponents, that $x^a \cdot x^b=x^{a+b}$. As you said, the first digit of the number can be $2,3,5$ or $7$. Each of these has been corresponded to a parameter, $x$, exponentiated to that power. All of these choices has been added and then multiplied $n$ times, since we have the same choices every time. So, we would get every possible sum of digits for an $n$ digit number, as every possible sum appears in the exponent*.

Now, the divisibility rule by $3$ states that a number is divisible by $3$ iff the sum of its digits is divisible by $3$. Hence, in the expression $(x^2+x^3+x^7+x^9)^n$, we find out the number of terms in which this sum evaluated to $3$, or $6$, or $9$, and so forth. This is given by the respective coefficients of $x^3$, $x^6$, $x^9$, etc. Hence what we need to do is find the sum of these coefficients. This can be done using $3^{rd}$ roots of unity, as has been shown in the solution.

*: if you are having trouble grasping this concept, it might help to start with small cases. For example, try to calculate the number of $3$ digit numbers with digits among $\{2,3\}$ which are divisible by 3.

Edit: The reason why we're adding powers of $x$ in each term of product is this- imagine we multiply out the product we had obtained. If $\overline{a_1 a_2 a_3...a_n}$ is a possible combination with $a_i\in \{2,3,7,9\}$ for $1\leq i \leq n$, then $x^{a_1+a_2+a_3+...+a_n}$ would appear in this expansion exactly once.

Now if the exponent is equal to, say, $3k$ for some particular $k$, then all such combinations of $a_i$ where $\sum a_i=3k$ also appear exactly once. Hence, the coefficient of $x^{3k}$ would represent the number of $n$-digit numbers, the sum of whose digits is $3k$.