Just about few hours ago I just happened to read a nice quibble from a friend of mine which was hyper-centrifuged on "why is that a person(at least the majority) would not be able to lead a life as a loner". Well, I was really excited about this quote!. So, I felt that I should be able to prove it mathematically- So, I picked up my pen (yeah, ofcouse my balck pen :P - No prizes for guess ;) ) and took my way with the proof; and this was a dove-tail of the entire pipe-line.
Lets start from the grass-roots; The LONER PROBLEM requires us to relate and justify that from a set of 2n objects (Boys or girls) we would be able to associate atelast n-pairs as partially or fully functional dependent. Ok for our simplicity lets have a sex ratio of 1:1 and let our aim be to match 'n' girsl with the set of 'n' boys(or girls- But yeah, since we want to make it simple we'll go by the old tradition...lolz!). So, each girl (after a long and no doubt exhausting deliberation) submits a list of boys she likes. We also make an assumption that being of noble character no boy will break a heart of a girl who likes him by turning her(or him) down. So, although, girls appear to seize the initiative by advertising their preferences, the situation is quite symmetric and is best represented by a sparse matrix. An element aij in row i and column j is 1 iff there is a dependency between the girl #i and the boy number #j and is feasible. aij is 0, otherwise. Sometimes all the girls can be given away, sometimes no dependency is also possible.
The dependency condition can be formulated in several equivalent ways:
1. Every set of r girls, 1 ≤ r ≤ n depends on at least r boys.
Pick up any s columns. Concentrate on rows that have at least one 1 in the selected columns. The number of such rows must not be less than s.
2. Every set of s boys, 1 ≤ s ≤ n depends on at least s girls.
Pick up any r rows. Concentrate on columns that have at least one 1 in the selected rows. The number of such columns must not be less than r.
3. No zero r by s submatrix may satisfy r + s > n.
If such a matrix exists then some r girls can marry only (n - s) boys outside the submatrix. Since r > n - s, there are just too few boys to satisfy all r girls.
Proof 1.
The necessecity is obvious. The sufficient part is shown by induction. The case of n = 1 and a single pair being dependent on each other requires a mere technicality to arrange a dependency. Assume we have already established the theorem for all k by k matrices with k < n. For the case of n girls and boys, the dependency may be satisfied with room to spare or just barely. In the first case, there is enough room for the first girl to be dependent on whomever she likes; the dependency condition will still be satisfied for the remaining (n - 1) and (n - 1) boys. Indeed, every 0 < r < n girls like more than r boys. One of those boys may have been the one who is dependent on the first girl - but without whom there are still at least r boys. So, after striking off any eligible pair we shall be left with (n - 1) girls and boys for whom the dependency condition still holds and, by the inductive hypothesis, complete match is possible.
In the second case, there are r < n girls who like exactly r boys. By the inductive hypothesis, a complete match exists for these r girls so they can be dependent to the r boys they like. The trick is to show that the remaining girls can be matched to the remaining boys. Consider any s of the remaining n - r girls. The r already dependent girls plus these s girls must like at least r + s boys as assured by the second condition. Since the r already dependent girls don't like boys other than the r they are dependent on, the s girls must like s boys other than the already dependent boys. Hence the remaining n - r girls satisfy the dependency condition with the undependent boys; and so a complete match is possible for the remaining girls with the remaining boys, providing a complete match for all the girls.
Another proof based on the Inclusion-Exclusion principle deals directly with subsets A1, A2, ..., An and establishes existence of an SDR. The Inclusion-Exclusion principle asserts that for any two finite sets A and B |A∪B| + |A∩B| = |A| + |B|, where vertical bars denote the cardinality (the number of elements) of a set. Lets prove that now. [ I know its too hard to digest, but, yeah..Lets continue this for another 5 minutes- It real fun! ]
Assuming that the dependency condition holds for the sets A1, A2, ..., An, let the sets be depleted until a family F = {B1, B2, ..., Bn} is reached such that removal of 1 more element from any of the Bi would cause the dependency condition to be violated. We assert that each member of F consists of a single element; because these elements are distinct (by the dependency condition), F itself is the required SDR. Suppose, on the contrary, that, say B1 has 2 elements, Let's say, B1 contains at least two elements, x and y. By the minimality of the collection, removal of either x or y would violate the matching condition.
Therefore, there exist two sets of indices P and Q such that
X = (B1-{x})∪(∪{Bi: i P}) and Y = (B1-{y})∪(∪{Bi: i Q}) with |X| ≤ |P| and |Y| ≤ |Q|. Consequently, by the Inclusion-Exclusion priciple,
(*) |X∪Y| + |X∩Y| = |X| + |Y| ≤ |P| + |Q|
On the other hand, X∪Y = B1∪(∪{Bi: i P∪Q}) and X∩Y = ∪{Bi: i P∩Q} the dependency condition gives
|X∪Y| ≥ 1 + |P∪Q| and |X∩Y| ≥ |P∩Q|.
From here, with one more application of the Inclusion-Exclusion principle, we obtain
|X∪Y| + |X∩Y| ≥ 1 + |P∪Q| + |P∩Q| = 1 + |P| + |Q| > |P| + |Q|
which contradicts (*).
Lolz..aint that some sense?!
Lets start from the grass-roots; The LONER PROBLEM requires us to relate and justify that from a set of 2n objects (Boys or girls) we would be able to associate atelast n-pairs as partially or fully functional dependent. Ok for our simplicity lets have a sex ratio of 1:1 and let our aim be to match 'n' girsl with the set of 'n' boys(or girls- But yeah, since we want to make it simple we'll go by the old tradition...lolz!). So, each girl (after a long and no doubt exhausting deliberation) submits a list of boys she likes. We also make an assumption that being of noble character no boy will break a heart of a girl who likes him by turning her(or him) down. So, although, girls appear to seize the initiative by advertising their preferences, the situation is quite symmetric and is best represented by a sparse matrix. An element aij in row i and column j is 1 iff there is a dependency between the girl #i and the boy number #j and is feasible. aij is 0, otherwise. Sometimes all the girls can be given away, sometimes no dependency is also possible.
The dependency condition can be formulated in several equivalent ways:
1. Every set of r girls, 1 ≤ r ≤ n depends on at least r boys.
Pick up any s columns. Concentrate on rows that have at least one 1 in the selected columns. The number of such rows must not be less than s.
2. Every set of s boys, 1 ≤ s ≤ n depends on at least s girls.
Pick up any r rows. Concentrate on columns that have at least one 1 in the selected rows. The number of such columns must not be less than r.
3. No zero r by s submatrix may satisfy r + s > n.
If such a matrix exists then some r girls can marry only (n - s) boys outside the submatrix. Since r > n - s, there are just too few boys to satisfy all r girls.
Proof 1.
The necessecity is obvious. The sufficient part is shown by induction. The case of n = 1 and a single pair being dependent on each other requires a mere technicality to arrange a dependency. Assume we have already established the theorem for all k by k matrices with k < n. For the case of n girls and boys, the dependency may be satisfied with room to spare or just barely. In the first case, there is enough room for the first girl to be dependent on whomever she likes; the dependency condition will still be satisfied for the remaining (n - 1) and (n - 1) boys. Indeed, every 0 < r < n girls like more than r boys. One of those boys may have been the one who is dependent on the first girl - but without whom there are still at least r boys. So, after striking off any eligible pair we shall be left with (n - 1) girls and boys for whom the dependency condition still holds and, by the inductive hypothesis, complete match is possible.
In the second case, there are r < n girls who like exactly r boys. By the inductive hypothesis, a complete match exists for these r girls so they can be dependent to the r boys they like. The trick is to show that the remaining girls can be matched to the remaining boys. Consider any s of the remaining n - r girls. The r already dependent girls plus these s girls must like at least r + s boys as assured by the second condition. Since the r already dependent girls don't like boys other than the r they are dependent on, the s girls must like s boys other than the already dependent boys. Hence the remaining n - r girls satisfy the dependency condition with the undependent boys; and so a complete match is possible for the remaining girls with the remaining boys, providing a complete match for all the girls.
Another proof based on the Inclusion-Exclusion principle deals directly with subsets A1, A2, ..., An and establishes existence of an SDR. The Inclusion-Exclusion principle asserts that for any two finite sets A and B |A∪B| + |A∩B| = |A| + |B|, where vertical bars denote the cardinality (the number of elements) of a set. Lets prove that now. [ I know its too hard to digest, but, yeah..Lets continue this for another 5 minutes- It real fun! ]
Assuming that the dependency condition holds for the sets A1, A2, ..., An, let the sets be depleted until a family F = {B1, B2, ..., Bn} is reached such that removal of 1 more element from any of the Bi would cause the dependency condition to be violated. We assert that each member of F consists of a single element; because these elements are distinct (by the dependency condition), F itself is the required SDR. Suppose, on the contrary, that, say B1 has 2 elements, Let's say, B1 contains at least two elements, x and y. By the minimality of the collection, removal of either x or y would violate the matching condition.
Therefore, there exist two sets of indices P and Q such that
X = (B1-{x})∪(∪{Bi: i P}) and Y = (B1-{y})∪(∪{Bi: i Q}) with |X| ≤ |P| and |Y| ≤ |Q|. Consequently, by the Inclusion-Exclusion priciple,
(*) |X∪Y| + |X∩Y| = |X| + |Y| ≤ |P| + |Q|
On the other hand, X∪Y = B1∪(∪{Bi: i P∪Q}) and X∩Y = ∪{Bi: i P∩Q} the dependency condition gives
|X∪Y| ≥ 1 + |P∪Q| and |X∩Y| ≥ |P∩Q|.
From here, with one more application of the Inclusion-Exclusion principle, we obtain
|X∪Y| + |X∩Y| ≥ 1 + |P∪Q| + |P∩Q| = 1 + |P| + |Q| > |P| + |Q|
which contradicts (*).
Lolz..aint that some sense?!
16 Thoughts have been Sprinkled!, Your Take? :
Post a Comment
Whatta thought!!!!!!
Man..this is heights of mathematics!!!
bows to thee maestro..
I agree to it in all aspects and u know why!!!
Is it that u never change?
hehe hehe..
Man!, you've got brains like no one else!
!!
Bingo!! and Cheers!!
But, somehow the second proof sounded more mathematical and more explicit than the first!!
As always B for Baggy and B for Brilliance!
ROTFL!!!
AWESOME!!!
Where is the link to the inspiration?!!?
loved the way you mingled up maths with fun,pun and logic!
So very you!
hehe..!
baggy, you OOBTs are always OHTs for me..:(
lol lol..see splitology..
:))))
This is a lil too much to take in at the first shot!
But anyways superb thoughts there!!!
And hats off to this great mathie wonder!
Now i wonder what else comes out as such proofs!!! :)
Being a loner myself .. I never equated it to the number factor. Still, struggling, I enjoyed the journey.
I am glad that each one of you enjoyed and scratched your head inside out!..
:)
And about the thoughts being crap..U all know me for more than a decade dont you?!
I have no words!
lolz!
Well, dearie.
I can only say that with math you can prove anything, including proving that i'm wrong..:)
hehe hehe!
yeah, my pen knows you very well as an acquaint ..
I was wondering as to why it was shouting slogans of "hail karen" last week..I get more conspicuous things now..:P
Sorry for the trouble ma'am.
Well, the proof was a pretty generic one. And from being a non-loner i meant that you would have atleast one "human" who'd care for you or there would be atleast one "human" for whom you care for. It need not necessarily be spouse or boy/girl friends..
Thanks for your thoughts!
I am glad that you liked the journey!- I am honored at the check-post!
Post a Comment