|
Author |
Message |
crooks_dwayne@yahoo.com science forum beginner
Joined: 19 Oct 2005
Posts: 4
|
Posted: Wed Oct 19, 2005 8:17 pm Post subject:
number of functions
|
|
|
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:> |
|
Back to top |
|
 |
Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
Posted: Thu Oct 20, 2005 11:01 am Post subject:
Re: number of functions
|
|
|
crooks_dwayne@yahoo.com wrote:
Quote: | 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.
|
I get 4^1998 * 2 for an answer.
The number of functions from
f:{1,2,...,1999} -> {2000,2001,2002,2003,2004} where
f(1)+f(2)+...+f(1999) is odd is a MUCH harder problem.
--- Christopher Heckman |
|
Back to top |
|
 |
crooks_dwayne@yahoo.com science forum beginner
Joined: 19 Oct 2005
Posts: 4
|
Posted: Thu Oct 20, 2005 11:52 pm Post subject:
Re: number of functions
|
|
|
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. |
|
Back to top |
|
 |
Matthew Roozee science forum beginner
Joined: 22 Oct 2005
Posts: 7
|
Posted: Sat Oct 22, 2005 7:17 am Post subject:
Re: number of functions
|
|
|
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:
Quote: | 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:
|
|
|
Back to top |
|
 |
Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
Posted: Sat Oct 22, 2005 7:40 am Post subject:
Re: number of functions
|
|
|
crooks_dwayne@yahoo.com wrote:
Quote: | 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.
|
Here's the problem:
crooks_dwa...@yahoo.com wrote:
Quote: | 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.
|
You can choose f(1), f(2), ..., f(1998) to be any of 2000, 2001, 2002,
2003. Now, there are only two ways to choose f(1999) to make the sum
even (and two to make it odd), no matter how f(1), f(2), ..., f(1998)
are chosen. For instance, if
f(1) + f(2) + ... + f(1998) is even, then f(1999) must be 2001 or 2003.
So the total number of functions is 4^1998 * 2.
Now my other comment should be clear; if we replace
{2000,2001,2002,2003} with {2000,2001,2002,2003,2004}, the problem
becomes MUCH harder; if you try the procedure above, then you may have
2 or 3 choices for f(1999), so you just can't multiply a bunch of 5's
times a number k.
--- Christopher Heckman |
|
Back to top |
|
 |
Matthew Roozee science forum beginner
Joined: 22 Oct 2005
Posts: 7
|
Posted: Sat Oct 22, 2005 7:41 am Post subject:
Re: number of functions
|
|
|
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:
Quote: | crooks_dwayne@yahoo.com wrote:
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.
I get 4^1998 * 2 for an answer.
The number of functions from
f:{1,2,...,1999} -> {2000,2001,2002,2003,2004} where
f(1)+f(2)+...+f(1999) is odd is a MUCH harder problem.
--- Christopher Heckman
|
|
|
Back to top |
|
 |
crooks_dwayne@yahoo.com science forum beginner
Joined: 19 Oct 2005
Posts: 4
|
Posted: Sat Oct 22, 2005 4:11 pm Post subject:
Re: number of functions
|
|
|
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. |
|
Back to top |
|
 |
Matthew Roozee science forum beginner
Joined: 22 Oct 2005
Posts: 7
|
Posted: Sat Oct 22, 2005 10:58 pm Post subject:
Re: number of functions
|
|
|
crooks_dwayne@yahoo.com wrote:
Quote: | 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
|
I think you mean Case 2: even + even + even + odd = odd
Quote: | 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)
|
This is where the real problem lies. What you have written describes
dropping identical balls into numbered boxes... you are treating any two
mappings to the same value as equivalent. That is, a function
f(1)=2000, f(2)=2001 is considered the same as f(1)=2001, f(2)=2000 by
your method. The problem as stated requires numbered balls dropped into
numbered boxes to use this approach.
Quote: | 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.
|
- Matt |
|
Back to top |
|
 |
crooks_dwayne@yahoo.com science forum beginner
Joined: 19 Oct 2005
Posts: 4
|
Posted: Sun Oct 23, 2005 2:56 am Post subject:
Re: number of functions
|
|
|
Thank you very much for all the helpful information. |
|
Back to top |
|
 |
Google
|
|
Back to top |
|
 |
|
The time now is Tue Apr 24, 2018 3:00 am | All times are GMT
|
Copyright © 2004-2005 DeniX Solutions SRL
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|