number of functions

crooks_dwayne@yahoo.com · science forum beginner Joined: 19 Oct 2005 Posts: 4

The problem:
Determine the number of functions
f:{1,2,...,1999}->{2000,2001,2002,2003} satisfying the condition that
f(1)+f(2)+...+f(1999) is odd.

The book i got this problem from has no solution for it. I think i have
solved it and would just like to get my answer verified. If someone can
try to solve and post there answer I would gladly post my results also.

Thanx:>

Proginoskes · science forum Guru Joined: 29 Apr 2005 Posts: 2593

crooks_dwayne@yahoo.com wrote:

crooks_dwayne@yahoo.com · science forum beginner Joined: 19 Oct 2005 Posts: 4

Can you plz expand on your result and tell me how you got it because I
got something totally different.

Here's my ans: 2*[C(1002,3) + C(1001,3)]

My solution is kinda long so only if you insist I would put up my
solution.

Matthew Roozee · science forum beginner Joined: 22 Oct 2005 Posts: 7

I looked at this as follows:

Think of f as mapping to a two dimensional set ({E,O},{L,H}).
Here, E = Even, O = Odd, L = Low, and H = High.
Thus the four values are:
(E,L)=2000 (E,H)=2002 (O,L)=2001 (O,H)=2003

So if we think of f = (f1, f2) where f1: 1...1999 --> E,O and f2:
1...1999 --> O,H we can just multiply the number of each type of function.

There are 2^1999 possible choices for f1.
For f2 to satisfy that our sum is odd, f2 must map an odd number of
values to O. How many ways can f2 do this? There are a total of 2^1999
possible choices for f2. The total number of functions that have x odd
targets and 1999-x even targets is the same as the total number of
functions that have x even targets and 1999-x odd targets. That is,
half of our 2^1999 possible functions will satisfy our odd sum
requirement for f2.

Multiplying together, we get (2^1999)(2^1998)=(2^3997)

- Matt

crooks_dwayne@yahoo.com wrote:

Proginoskes · science forum Guru Joined: 29 Apr 2005 Posts: 2593

crooks_dwayne@yahoo.com wrote:

Matthew Roozee · science forum beginner Joined: 22 Oct 2005 Posts: 7

The case of 5 target values is a harder problem...

Let S = {2000,2001,2002,2003,2004}
Let A(n) be defined as the number of functions from {1,2,...n} --> S
whose sum is odd and let B(n) be defined as the number of functions from
{1,2,...,n} --> S whose sum is even.

Then
A(n) = 3*A(n-1) + 2*B(n-1)
B(n) = 2*A(n-1) + 3*B(n-1)
with initial conditions A(1) = 2, B(1) = 3

Re-writing the first equation gives:
B(n-1) = [A(n) - 3*A(n-1)]/2 and
B(n) = [A(n+1) - 3*A(n)]/2

Substituting into the second equation and multiplying by 2 gives:
A(n+1) - 3*A(n) = 3*A(n) - 9*A(n-1) + 4*A(n-1) or
A(n+1) = 6*A(n) - 5*A(n-1)

The characteristic equation for A has roots r1 = 1 and r2 = 5.

Thus A(n) = c1 + c2*(5^n)

A(0) = 0 = c1 + c2
A(1) = 2 = c1 + c2*(5)

or c1 = -1/2 and c2 = +1/2

and A(n) = (5^n - 1)/2

so A(1999) = (5^1999-1)/2

- Matt

Proginoskes wrote:

crooks_dwayne@yahoo.com · science forum beginner Joined: 19 Oct 2005 Posts: 4

Here's my solution: (plz tell me if this reasoning is flawed in any
way)

Now,
f(1) + f(2) + ... + f(1999) = a*2000 + b*2001 + c*2002 + d*2003
....(1)
and
a + b + c + d = 1999
....(2)

where a,b,c,d are non-negative integers representing the number of
times the
function maps to 2000,2001,2002 and 2003 respectively.

Also, the following constraints are realized if (1) must have an odd
sum:
- the terms a*2000 and c*2002 are always even regardless a or c is even
or odd
- the terms b*2001 and d*2003 is even when b, d is even and odd when b,
d is odd

Hence the only way (1) can be odd is if we have:
Case 1: even + odd + even + even = odd
or
Case 2: even + even + odd + even = odd

Case 1: corresponds to the following,

- a is even or odd, b is odd, c is even or odd and d is even

If a is even and c is even then in (2) we have
2p + (2q+1) + 2r + 2s = 1999 where p,q,r,s >= 0
i.e. p + q + r + s = 999

The no. of solutions is C(999+4-1,4-1) = C(1002,3)

If a is odd and c is odd then in (2) we have

(2p+1) + (2q+1) + (2r+1) + 2s = 1999 where p,q,r,s >= 0
i.e. p + q + r + s = 998

The no. of solutions is C(998+4-1,4-1) = C(1001,3)

The other two possibilities, namely:
- if a is even and c is odd or
- if a is odd and c is even
are not possible given the constraints and hence they give no solutions

Hence in case 1 we get C(1002,3)+C(1001,3) solutions.

Since case 2 is symmetric to case 1 we get the same no. of solutions.

Hence the total no. of solutions is N = 2*(C(1002,3)+C(1001,3))
which is equal to the total number of solutions to the original
problems.

Note: A different assignment to the values a,b,c,d means a different
function is being used and since the two problems are in a 1-1
correspondence with each other i believe my approach gives the right
answer. Plz correct me if I'm wrong.

Matthew Roozee · science forum beginner Joined: 22 Oct 2005 Posts: 7

crooks_dwayne@yahoo.com wrote:

crooks_dwayne@yahoo.com · science forum beginner Joined: 19 Oct 2005 Posts: 4

Thank you very much for all the helpful information.

Google