49th Mathematical Olympiad in Ukraine

a. If we take $m=1$, then we will get that $k+1+n^1=2009^n$ or that $k=2009^n-1-n$. It is clear that this will be a solution: $(n,m,k)=(n,1,2009^n-n-1)$.

b. If $m=1$, then our equation comes to $k+1+n=2009^n$, which holds for the only value of $k$. Thus, new solutions can exist only when $m\ge 2$.

Consider $n=2009^s$, where $s$ is natural. Then $(2009^{s{m}^k})<k+m^k+n^{m^k}=2009^{2009^s}$, whence $s\cdot m^k<2009^s$, and so $m^k<2009^s$. Let us make use of the following lemma:

Lemma. For every natural $n$: $2^n\ge n$.

This lemma implies that for $m\ge 2$ we have $m^k\ge 2^k\ge k$, i.e. $k+m^k<2009^s+2009^s=2\cdot 2009^s$. But $k+m^k=2009^{2009^s}-n{m}^k=2009^{2009^s}-2009^{s-m^k}$. Now since $2009^s>2\cdot 1000^s>2\cdot 2^s\ge 2s$ and $m\ge 2$, we get that the right side is divisible by $2009^{2s}$. But at the same time $1<k+m^k<2\cdot 2009^s$ and thus the left side cannot be divisible by $2009^{2s}$. The obtained contradiction shows that for $n=2009^s$ the solution is unique. And it is evident that there are infinitely many such $n$.