Author |
Topic: Combinatorics (Read 1340 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
Combinatorics
« on: Feb 10th, 2008, 3:05am » |
 Quote  Modify
|
How to prove that for large N, the greatest integer K for which N*(N-1)(N-2)*....(N-K)/(N^K) is
greater than 0.5 is approximately sqrt(N) ?
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Combinatorics
« Reply #1 on: Feb 10th, 2008, 9:12am » |
Quote Modify
|
Isn't it the birthday paradox ... 
http://en.wikipedia.org/wiki/Birthday_paradox
Approximation by e0/Ne1/N...eK/N=e(K+1)K/2N
As the expression should be constant K is proportional to sqrt N.
|
| « Last Edit: Feb 10th, 2008, 9:23am by Hippo » |
IP Logged |
|
|
|
Albert_W.
Newbie
Posts: 12
|
|
Re: Combinatorics
« Reply #2 on: Jun 17th, 2008, 11:11pm » |
Quote Modify
|
I have a problem that is too tough for me to solve.
Marriage Theorem: The marriage problem requires us to match n girls with the set of n boys.
However, suppose we have N men and M women.
Furthermore, suppose each man makes a list of women that he is willing to marry.
Now suppose we have the property that if any one of the given men (from 1 to N) is ignored, then the remaining N-1 men can be paired off with the M women such that each man has a wife. However, let it be such that if all men are considered, then it is not possible for all N men to be married.
The question:
How to find integers N and M (representing men and women) and then find N subsets of M (representing the N different lists of women each man makes for women they are willing to marry) such that the above property holds, or prove that such construction cannot occur?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Combinatorics
« Reply #3 on: Jun 18th, 2008, 12:20am » |
Quote Modify
|
on Jun 17th, 2008, 11:11pm, Albert_W. wrote:I have a problem that is too tough for me to solve.
Marriage Theorem: The marriage problem requires us to match n girls with the set of n boys.
However, suppose we have N men and M women.
Furthermore, suppose each man makes a list of women that he is willing to marry.
Now suppose we have the property that if any one of the given men (from 1 to N) is ignored, then the remaining N-1 men can be paired off with the M women such that each man has a wife. However, let it be such that if all men are considered, then it is not possible for all N men to be married.
The question:
How to find integers N and M (representing men and women) and then find N subsets of M (representing the N different lists of women each man makes for women they are willing to marry) such that the above property holds, or prove that such construction cannot occur?
|
|
You could take 3 men, and two women. Clearly not all men can be paired off with a woman.
Now suppose that man A only want to marry woman #1, man B only wants to marry woman #2, and man C is willing to marry either. Then eliminating any of the three men will allow you to pair off the other two. (You can easily generalize this for N=M+1)
It may be trickier if all the subsets need to be the same size.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Combinatorics
« Reply #4 on: Jun 18th, 2008, 1:28am » |
Quote Modify
|
Since any N-1 men can be married, we know that for any subset of the men of size k < N, there are at least k women who can be married to at least one of those men.
Now it follows from Hall's marriage theorem that all N men can be married iff there are at least N women, ignoring the women who can't be married at all.
|
| « Last Edit: Jun 18th, 2008, 1:31am by Eigenray » |
IP Logged |
|
|
|
Albert_W.
Newbie
Posts: 12
|
|
Re: Combinatorics
« Reply #5 on: Jun 18th, 2008, 11:15am » |
Quote Modify
|
Please correct me if i'm wrong:
In order to ensure that not all N men can be married off, we can just take M = N - 1 for the number of women. Doing this such that we still have the property that any N-1 men can be married is easy so long as the conditions of Hall's theorem are met. Consider the following example for instance.
M1 = (1,3)
M2 = (1,3,4)
M3 = (4,2)
M4 = (3,2)
M5 = (1).
We see that any proper subset of size k has at least k elements, therefore by Hall's theorem we have that any 4 of the 5 men can be married, but clearly we cannot marry off all 5 men since there are only 4 women.
|
|
IP Logged |
|
|
|
Albert_W.
Newbie
Posts: 12
|
|
Re: Combinatorics
« Reply #6 on: Jun 18th, 2008, 11:08pm » |
Quote Modify
|
on Jun 18th, 2008, 11:15am, Albert_W. wrote:Please correct me if i'm wrong:
In order to ensure that not all N men can be married off, we can just take M = N - 1 for the number of women. Doing this such that we still have the property that any N-1 men can be married is easy so long as the conditions of Hall's theorem are met. Consider the following example for instance.
M1 = (1,3)
M2 = (1,3,4)
M3 = (4,2)
M4 = (3,2)
M5 = (1).
We see that any proper subset of size k has at least k elements, therefore by Hall's theorem we have that any 4 of the 5 men can be married, but clearly we cannot marry off all 5 men since there are only 4 women. |
|
I'm sorry for asking again: is this correct?
A friend and classmate wrote the solution.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Combinatorics
« Reply #7 on: Jun 19th, 2008, 1:19am » |
Quote Modify
|
Is assumption in Hall's theorem restricted to PROPER subsets?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Combinatorics
« Reply #8 on: Jun 19th, 2008, 5:59am » |
Quote Modify
|
on Jun 18th, 2008, 11:08pm, Albert_W. wrote:
I'm sorry for asking again: is this correct?
A friend and classmate wrote the solution.
|
|
It is an example of a situation which satisfies the conditions laid down in the problem statement. Eigenray has already stated the precise condition for all N men to get married, given that any N-1 of them can be - namely that, between them, they are willing to marry N different women.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print