Here is a partial attempt at an answer. If we're lucky, it will attract someone's attention (Gjergji? Noam?) and they will resolve the question.

If there are enough sums of the form $a^ab^b$ the result is most likely true for a given $n$ and any prime $p$. Note that are not enough sums when $4 > n$. An equivalent formulation, using $c=a+1$ and $b=d+1$, is to find nonnegative $a,b$ with $a+b=n$ such that $a^ab^b \neq c^cd^d$ mod $p$ .

Suppose $k$ is coprime to $p-1$. If  $a^ab^b \neq n^n$ mod p, then $(ak)^a(bk)^b \neq (nk)^n$ mod $p$ and the inequality holds when everything is raised to the power $k$. If one is lucky to find a satisfying decomposition of $nk$ into $ak$ and $bk$, then one can reverse the process, again assuming $k$ is coprime to $p-1$ (because then $k$th roots mod $p$ are unique).

I will post more as ideas occur to me on this probllem.

Gerhard "Ask Me About System Design" Paseman, 2011.07.31

Here is a partial attempt at an answer. If we're lucky, it will attract someone's attention (Gjergji? Noam?) and they will resolve the question.

If there are enough sums of the form $a^ab^b$ the result is most likely true for a given $n$ and any prime $p$. Note that are not enough sums when $4 > n$. An equivalent formulation, using $c=a+1$ and $b=d+1$, is to find nonnegative $a,b$ with $a+b=n$ such that $a^ab^b \neq c^cd^d$ mod $p$ .

Suppose $k$ is coprime to $p-1$ (Edit: and $p > k$). If $a^ab^b \neq n^n$ mod p, then $(ak)^a(bk)^b \neq (nk)^n$ mod $p$ and the inequality holds when everything is raised to the power $k$. If one is lucky to find a satisfying decomposition of $nk$ into $ak$ and $bk$, then one can reverse the process, again assuming $k$ is coprime to $p-1$ (because then $k$th roots mod $p$ are unique).

I will post more as ideas occur to me on this probllem.

Gerhard "Ask Me About System Design" Paseman, 2011.07.31