Demo*graph*ics

I claim that it is necessary and sufficient that $n$ is a power of $2$

First we show that it is necessary that $n$ is a power of $2$ . Suppose that there in fact is some such coloring. WLOG consider a color, call it $\alpha$ . Draw arrows from vertex $v$ to vertex $w$ whenever $v$ and $w$ are adjacent and $w$ has color $\alpha$ . Note that it is possible for $v$ to point to $w$ while $v$ points to $w$ . The total number of such arrows is $2^n$ because by the neighborhood diversity condition we have exactly one leaving each vertex. Alternatively, let the number of vertices with color $\alpha$ be $A$ . Then the number of arrows is $nA$ , by counting the number of arrows (exactly $n$ ) that terminate in a given vertex with color $\alpha$ . So $nA=2^n\implies n\mid 2^n$ , as desired.

Now for the construction! Let $n=2^r$ . We can naturally assign a unique vector in $\mathbb F_2^{2^r}$ . The central insight is to design a "characteristic function" $\chi:\mathbb F_2^{2^r}\to \mathbb F_2^r$ and to let $\chi(v)$ be the "color" of the vertex represented by $v$ . Consider the natural bijection that takes entries of $v\in\mathbb F_2^{2^r}$ to $\mathbb F_2^r$ (say some entry of $v$ maps to $v'$ ). Now let $e_i(v')$ give the $i^{\text{th}}$ entry of $v'\in\mathbb F_2^r$ , and let $S_i$ be the set of entries of $v$ with $e_i(v)=1$ . Finally, let $C(v')$ give the value (either $0$ or $1$ ) at said entry in $v$ . We will let $\chi(v)$ be the unique element of $\mathbb F_2^r$ satisfying $e_i\left(\chi(v)\right)=\Sigma_{v'\in S_i}C(v')$ , where the equality occurs in $\mathbb F_2$ . So we need only show that given a vertex of the original hypercube, represented by $v$ , there is a unique adjacent vertex, represented by $w$ , with characteristic $a\in\mathbb F_2^r$ . But we can directly construct such a vertex; just switch the entry of $v$ represented by $\chi(v)-a$ . Uniqueness follows by size (a surjection between finite sets of equal cardinality is necessarily a bijection).

Thus the answer is $1+2+\cdots+512=\boxed{1023}$