3. Consider all 100-digit positive integers such that each decimal digit of these equals $2,3,4,5,6$, or 7 . How many of these integers are divisible by $2^{100}$ ?
Pavel Kozhevnikov
Say
$$F_n=\{\text{N: N is $n$-digit interger with digits in $\{2,3,4,5,6,7\}$ such that $2^n\mid N$}\}$$and $f_n=|F_n|$.
Clearly $f_1=3$. Say $10^{n}x+y\in F_{n+1}$, where $x\in\{2,3,4,5,6,7\}$. Then
$$2^{n}\mid 2^{n+1}\mid 10^{n}x+y\to 2^n\mid y\to y\in F_n.$$
Now, say $y\in F_n$ is of the form $2^n\cdot j$. Then we want all the $x$ such that
$$\mid 2^{n+1}\mid 10^{n}x+y\to 2\mid 5^nx+j\to 2\mid x+j$$So, $x$ is determined by the parity of $j$, and as in $\{2,3,4,5,6,7\}$ we have same number of odd and even, then for each $y$ in $F_n$ there is exactly 3 $x$ such that $10^{n}x+y\in F_{n+1}$.
Therefore, $f_{n+1}=3f_n\to f_n=3^n$ for each $n$ and in particular $f_{100}=3^{100}$.