Find number of functions

Question

Find the number of functions $f: \{1,2,3,\dots,1999\}\to\{2000,2001,2002,2003\}$ satisfying the condition that $f(1)+f(2)+f(3)+\dots+f(1999)$ is odd.

Upon first thought my try was that for any function $2000p+2001q+2002r+2003s$ is odd where $p, q, r, s$ are natural numbers which also satisfy $p+q+r+s=1999$ and hence $q, s$ must be odd. Using generating functions I found the answer but then the thought stuck me that I am asked to find the number of functions possible. So I would like to know how would one do such questions using the mapping technique or any other combinatorial method.

Answer 1

Using generating functions we may write the possiblities for each $x$ in the domain as:

$$z^{2000}+z^{2001}+z^{2002}+z^{2003}$$

then, since these possibilities hold for each $x\in \{1,\ldots,1999\}$ the combinations of these may be expressed as the product:

$$(z^{2000}+z^{2001}+z^{2002}+z^{2003})^{1999}=\sum_{k}N_kz^{k}$$

where $N_k$ is the number of mappings whose co-domain sum is $k$.

We only want to count the odd sums, so note that by substituting $z=1$ we get:

$$4^{1999}=\sum_{k}N_k$$

and by substituting $z=-1$ we get:

$$0=\sum_{k\text{ even}}N_k - \sum_{k\text{ odd}}N_k$$

then subtracting these gives:

$$4^{1999}-0=2\sum_{k\text{ odd}}N_k$$ $$\implies \sum_{k\text{ odd}}N_k=\frac{4^{1999}}{2}=2\cdot 4^{1998}\tag{Answer}$$

Answer 2

In $f$'s codomain, two elements are even and two are odd. We can arbitrarily set the result of $f$ for 1998 arguments, but then the parity of the result for the last argument is fixed. Thus there are $2\cdot4^{1998}$ functions $f$.

Answer 3

Without restrictions, there are $4^{1999}$ possible functions. Now, if $f$ is a function such that $f(1) + \cdots +f(1999)$ is odd, then $g(x) = 4003 - f(x)$ is a function such that $g(1) + \cdots + g(1999)$ is even, and similarily if $f$ has even sum then $g$ has odd sum.

In this way, we can pair up every single one of the $4^{1999}$ functions into pairs containing one function for which the sum is even, and one function for which the sum is odd (where one element of the pair is $4003$ minus the other). Thus exactly half of all the possible functions have odd sum. This gives $2\cdot 4^{1998}$.