Let $n\in \mathbb{Z}_{> 0}$. The set $S$ contains all positive integers written in decimal form that simultaneously satisfy the following conditions: each element of $S$ has exactly $n$ digits; each element of $S$ is divisible by $3$; each element of $S$ has all its digits from the set $\{3,5,7,9\}$ Find $\mid S\mid$
Problem
Source: MDA TST 2016
Tags: combinatorics
crezk
26.03.2019 17:18
I cant solve I have 154 ıq
WeakMathemetician
26.03.2019 17:58
This is not 200iq
DievilOnlyM
26.03.2019 18:05
crezk wrote: I cant solve I have 154 ıq Wow, high IQ, I think my IQ is less than 100
ftre775
27.03.2019 13:31
The legend says that you are not from China, you can't solve it.
benstein
27.03.2019 20:30
We can solve this using recursion. Say the desired value is $a_n$. Also, we have the number of integers using $n$ digits from ${3,5,7,9}$ that aren't divisible by $3$ is $4^n-a_n$. Then, we have the recursion $a_{n+1}=2a_n+(4^n-a_n)=4^n+a_n$. Then, we have $a_1=2$, so $a_n=\left(\sum_{i=0}^{n-1} 4^i\right) +1=\boxed{\frac{4^n+2}{3}}$.
claserken
27.03.2019 20:43
Define $f(x)=(x^3+x^5+x^7+x^9)^n=x^{3n}(1+x^2+x^4+x^6)^n$ as our generating function. Let $\omega=e^{\frac{2\pi i}{3}}$ be a primitive third root of unity. We simply need to compute $\frac{f(1)+f(\omega)+f(\omega^2)}{3}$. We have $f(1)=4^n$, $f(\omega)=1$, $f(\omega^2)=1$ by using $1+\omega+\omega^2=0$. Therefore, the answer is $\boxed{\frac{4^n+2}{3}}$.