, 2017

Solution:

Answer: $\left(1009,2^{1009}-2\right)$

I claim that $N$ can equal $0$ or $2^{i}$ for $1 \leq i \leq 1008$. We prove this now. Note that the average number of friends a toad has is also $2$. If there is a toad with $0$ friends, then clearly $N=0$. If a toad has $1$ friend, then it must be paired with its only friend, so we have reduced to a smaller case. Otherwise, all toads and frogs have exactly degree $2$, so the graph is a union of cycles. Each cycle can be paired off in exactly two ways. The number of cycles can range anywhere from $1$ to $1008$, and this completes the proof.

To construct all $N=2^{1}, 2^{2}, \ldots, 2^{1008}$, we can simply let our graph be a union of $i$ cycles, which would have $2^{i}$ matchings. Clearly we can choose any $i=1,2, \ldots, 1008$.

Therefore, $D=1009$ and $S=2^{1}+2^{2}+\cdots+2^{1008}=2^{1009}-2$.