wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Combinatorics
        
(Message started by: BenVitale on Feb 10th, 2008, 3:05am)
Title: Combinatorics
Post by BenVitale on Feb 10th, 2008, 3:05am
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) ?
Title: Re: Combinatorics
Post by Hippo on Feb 10th, 2008, 9:12am
Isn't it the birthday paradox ... ;)
http://en.wikipedia.org/wiki/Birthday_paradox
[hide]
Approximation by e0/Ne1/N...eK/N=e(K+1)K/2N

As the expression should be constant K is proportional to sqrt N.
[/hide]
Title: Re: Combinatorics
Post by Albert_W. on Jun 17th, 2008, 11:11pm
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?
Title: Re: Combinatorics
Post by towr on Jun 18th, 2008, 12:20am

on 06/17/08 at 23:11:45, 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.
Title: Re: Combinatorics
Post by Eigenray on Jun 18th, 2008, 1:28am
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.
Title: Re: Combinatorics
Post by Albert_W. on Jun 18th, 2008, 11:15am
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.
Title: Re: Combinatorics
Post by Albert_W. on Jun 18th, 2008, 11:08pm

on 06/18/08 at 11:15:44, 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.
Title: Re: Combinatorics
Post by Hippo on Jun 19th, 2008, 1:19am
Is assumption in Hall's theorem restricted to PROPER subsets?
Title: Re: Combinatorics
Post by rmsgrey on Jun 19th, 2008, 5:59am

on 06/18/08 at 23:08:09, 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.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board