5
$\begingroup$

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

My Attempt: Each integer in domain has $4$ choices and therefore the total number of functions is $f$ is $4^{1999}.$ Since there are an equal number of functions that yield odd or even result, we can directly write that the number of functions satisfying the above condition to be $2*4^{1998}.$ I am unsure about this last claim and would like to prove it (if it is true.)Also is the answer to this problem correct?

Edit $1$: I tried to proceed further in the following manner:

For a given mapping $f$ let the number of integers assigned to $2000,2001,2002$ amd $2003$ be $p,q,r$ and $s$ respectively, where $p,q,r,s\in \mathbb{Z}^+$. Therefore the sum in question can be written as $f(1)+f(2)+...+f(1999)=2000p+2001q+2002r+2003s.$ Clearly the sum will be odd iff $q+s$ is odd. Also note that $p+q+r+s=1999\Rightarrow p+r$ is even. On the other hand if we let $q+s$ as even then $p+r$ must be even. Now the number of values of $p,q,r$ and $s$ for which the above two lemmas hold is the same and therefore if we let $f$ to be the function which maps elements form $\{1,2,3,...,1999\}$ to $\{2000,2001,2002,2003\}$ such that $q+s$ is even and $g$ to be the function hich maps elements form $\{1,2,3,...,1999\}$ to $\{2000,2001,2002,2003\}$ such that $p+q$ is even we will get a bijection.(Maybe!)

$\endgroup$
8
  • $\begingroup$ You haven't justified why there are the same number of functions such that $f(1)+\cdots + f(1999)$ is odd as there are such that $f(1)+\cdots+f(1999)$. Can you exhibit a bijection between those collections of functions? That is, given a function such that $f(1)+\cdots+f(1999)$ is odd, define a corresponding function such that $g(1)+\cdots+g(1999)$ is even. Show that $f$ is the only function with $f(1)+\cdots+f(1999)$ odd and with corresponding function $g$, and that for any $g$ with $g(1)+\cdots+f(1999)$ even, there is an $f$ to which $g$ corresponds. $\endgroup$
    – kccu
    Nov 16, 2016 at 18:44
  • $\begingroup$ I am not aware of the technique you've mentioned in this comment. Anyways is the claim valid? $\endgroup$
    – Student
    Nov 16, 2016 at 18:49
  • $\begingroup$ Typo: the last sentence in my comment should say "any $g$ with $g(1)+\cdots+g(1999)$." Anyway, I'm asking you to justify why you think there are the same number of functions that yield an even or odd result. That's not always the case, for example if you had $f:\{1,2,\dots,1999\} \to \{2,4,6,8\}$. Then $f(1)+\cdots+f(1999)$ would always be even. What makes you think in your example you actually get the same number yielding even and odd results? $\endgroup$
    – kccu
    Nov 16, 2016 at 18:52
  • $\begingroup$ I do not know if the claim is true or not. But note that $\sum f(n)$ is odd if, and only if, one, and only one, of the following occurs: $f^{-1}(2001)$ is odd and $f^{-1}(2003)$ is even or $f^{-1}(2001)$ is even and $f^{-1}(2003)$ is odd. Since there are an equal number of functions in each case, we only need to count how many functions satisfy the first case. $\endgroup$ Nov 16, 2016 at 18:53
  • $\begingroup$ @kccu Please see the edit. $\endgroup$
    – Student
    Nov 16, 2016 at 18:55

4 Answers 4

4
$\begingroup$

Your result is correct. To justify the result, you can say that you have $4^{1998}$ choices of where to send the first $1998$ numbers. For each of them, there will be two complete functions that have odd sum, because if the sum of the first $1998$ values is odd, you can choose $2000$ or $2002$ for $f(1999)$ while if the sum of the first $1998$ values is even, you can choose $2001$ or $2003$ to get an odd sum, so there will be $2 \cdot 4^{1998}$ functions with odd sum.

To specifically justify the claim that half the functions have odd sum and half have even sum, pair up two functions that agree on the first $1998$ values, one with $f(1999)=2000$ and the other with $f(1999)=2001$ One of these will have even sum and one will have odd sum. Do the same with the other two values for $f(1999)$. You have shown a bijection between the set of functions that have even sum and the set of functions that have odd sum, so they must have the same number of members.

$\endgroup$
2
  • $\begingroup$ I got a different result, can you please review? $\endgroup$ Nov 16, 2016 at 19:10
  • $\begingroup$ @Ross Millikan Thank you for your answer. $\endgroup$
    – Student
    Nov 16, 2016 at 20:07
4
$\begingroup$

Take an arbitrary image of $f(k)$ for $k\in\{1,\ldots,1998\}$ so you have for each $k$ a value from $2001$ to $2003$ and so you have $4^{1998}$ choices. Now for $f(1999)$ and since the sum would be odd, we have only two choices: so the desired number is $2\times 4^{1998}$

$\endgroup$
1
$\begingroup$

The amount of elements mapped to $2001$ or $2003$ should be odd.

For each odd amount of $n$ elements chosen from $[1,1999]$:

  • The number of ways to map these elements to $2001$ or $2003$ is $2^n$
  • The number of ways to map the remaining $1999-n$ elements to $2000$ or $2002$ is $2^{1999-n}$

The answer is therefore:

$\sum\limits_{k=0}^{999}\binom{1999}{2k+1}\cdot2^{2k+1}\cdot2^{1999-(2k+1)}=$

$\sum\limits_{k=0}^{999}\binom{1999}{2k+1}\cdot2^{1999}=$

$2^{1999}\cdot\sum\limits_{k=0}^{999}\binom{1999}{2k+1}=$

$2^{1999}\cdot2^{1998}=$

$2^{3997}$

$\endgroup$
2
  • $\begingroup$ You missed the selection of which $n$ elements are odd, which gives a factor $1999 \choose n$ for each term. The answer is clearly way too small, as twice this is only $2000 \cdot 2^{1999}$ which is far smaller than the total of $4^{1999}$ functions. $\endgroup$ Nov 16, 2016 at 19:26
  • $\begingroup$ @RossMillikan: Indeed. After adding this factor, I get the same answer as yours. Thanks :) $\endgroup$ Nov 16, 2016 at 19:34
0
$\begingroup$

I did this one probably in a dumb way since i didn't see that the number of odd results is the same as the even one, but here we go:

The total number of such functions is $4^{1999}$

The number of sets that contain an even number of odd $f(x)$'s is: $$ \sum\limits_{k=0}^{999}\binom{1999}{2k}\cdot2^{2k}\cdot2^{1999-2k} $$ Where the term $2^{2k}\cdot2^{1999-2k}$ comes from the fact that there are 2 possible choices for even and odd numbers (this was kind of a trick since $2^{(2k)+(1999-2k)}=2^{1999}$, which is constant). Since we have 2 possibilities for both even and odd, namely {$2000,2002$} and {$2001,2003$} respectively, this is exactly half of: $$ \sum\limits_{j=0}^{1999}\binom{1999}{j}\cdot2^{j}\cdot2^{1999-j}= 4^{1999} $$ Half of it being (and this is where my mental autopilot went off and I realized my stupidity): $$ 2*4^{1998} $$ Hence we finally have: $$ 4^{1999}-2*4^{1998}=2*4^{1998} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .