Search   Memberlist   Usergroups
 Page 1 of 1 [9 Posts]
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:>
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
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.
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:
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
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
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.
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
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.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [9 Posts]
 The time now is Mon Mar 18, 2019 6:09 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am Generating function for Mathieu functions cosmicstring@gmail.com Math 1 Fri Jul 21, 2006 8:39 am a subset of natural number levine121323@yahoo.com Math 1 Fri Jul 21, 2006 6:17 am Entire functions, polynomial bounds david petry Math 2 Thu Jul 20, 2006 11:09 pm Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm