|
||
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:
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:
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:
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 |