Japan 2007

Let $f(n)$ be the number of ways to write $n$ as sum of nonnegative powers of $3$ and $f(0)=1$. We can write $n$ as sum of nonnegative powers of $3$ with $k$ $1$s iff $n-k$ is divisible by $3$. Let $n-k=3m$, then the number of ways to write $n$ as sum of nonnegative powers of $3$ with $k$ $1$s is equal to write $3m$ as sum of positive powers of $3$, and that is equal to $f(m)$. So we get $$f(n)=\sum _{0\le m\le n/3}f(m).$$ We can compute $f(100)$ by this relation. First we get $f(100)=f(0)+f(1)+\cdots +f(33)$. And from $f(0)=f(1)=f(2),f(3)=f(4)=f(5)=f(0)+f(1),\cdots ,f(30)=f(31)=f(32)=f(0)+\cdots +f(10),f(33)=f(0)+\cdots +f(11)$, we get $f(100)=34f(0)+31f(1)+\cdots +4f(10)+f(11)$. Applying the relation one more time we get $$\begin{array}{rl}f(100)& =(34+31+28)f(0)+(25+22+19)(f(0)+f(1))\\ & +(16+13+10)(f(0)+f(1)+f(2))\\ & +(7+4+1)(f(0)+f(1)+f(2)+f(3))\\ & =210f(0)+117f(1)+51f(2)+12f(3).\end{array}$$ From $f(0)=f(1)=f(2)=1$ and $f(3)=2$, we get $f(100)=402$.