1
$\begingroup$

enter image description hereenter image description here

Well, i tried hard to read the converse of the proof and i guess they are using some so-called procedure and tricks to make the proof work. However i can't figure out how it works. Can someone show how the tricks work and explain why it works? thx in advance for your help.

Edited: What i am confused with is starting from the sentence in the proof of the converse "As in the previous example, let girl $m+1$ may personally only know boys.......I don't quite understand they way it prove it with that method.

  • 2
    Can you be more specific? What exactly are you confused about?2012-02-07
  • 1
    related : http://math.stackexchange.com/q/45565/156602012-02-07
  • 1
    In my view this is an awful proof. It uses a steam engine instead the power of induction.2012-02-07
  • 0
    To Qiaochu Yuan:I have already edited what i am confused!2012-02-07
  • 0
    For accessibility and SEO, latexify the image. http://pastie.org/3338021 is a start; someone take over, please.2012-02-08
  • 0
    @Christian: In context I think it a rather good proof pædagogically: it’s elementary, it’s clearly explained, including discussion of a likely student error, it builds directly on a worked out example that immediately precedes it, and it’s pitched at a suitably elementary level for the intended audience.2012-02-08
  • 0
    @Brian M. Scott: The proof from the BOOK fits into a comment: When by chance any $r girls know $\geq r+1$ boys among them, one of the girls should take a boy she knows and refer the other $n-1$ girls to the induction hypothesis. If there is actually a set of $r girls which know exactly $r$ boys among them these $r$ girls should be served first, which is possible by induction, and for the remaining $n-r girls the hypothesis of the theorem is still satisfied, which implies that their demand can also be met.2012-02-08
  • 0
    @Christian: Proofs from the BOOK aren’t always the best ones to use with beginners, and brevity isn’t always a plus.2012-02-08
  • 0
    @Christian: I would not be convinced by that, at least at first sight: once you have married off one or more boys (no turning back) it is not instantly obvious that the remaining girls know enough boys.2012-02-09
  • 0
    Sorry if if I'm off-topic, but from which book does the proof come from ?2013-12-12

2 Answers 2

1

The key points are:

  • The hostess of the party is not engaged (yet)
  • The hostess knows some boys (at least one from the question) and invites them
  • Apart from the hostess, girls are only invited by their fiancés
  • Boys are only invited by girls who know them and are the hostess or already invited, so are not invited by their fiancées
  • At some stage there are at least as many boys as girls, as from the question a group of girls know at least as many boys
  • Since all but one of the girls are engaged and their fiancés are at the party, at least one of the boys is not engaged; concentrate on one of them
  • This unengaged boy knows at least one girl (engaged or the hostess) at the party since he was invited, so he can dance with a girl who invited him and he knows, and does
  • That engaged girl's fiancé knows at least one other girl (engaged or the hostess) at the party since he was invited before the unengaged boy, so he can dance with a girl who invited him and he knows, and does
  • That engaged girl's fiancé knows at least one other girl (engaged or the hostess) at the party since he was invited before the his fiancée's dancing partner, so he can dance with a girl who invited him and he knows, and does
  • The pattern continues back up the invitation chain until a boy who was invited originally by the hostess dances with her
  • Those of the original $m$ engaged girls and $m$ engaged boys not dancing (or not at the party) are all engaged pairs
  • Those dancing can break their existing engagements and become engaged to their dancing partners
  • So $m+1$ girls can find husbands from boys they know, proving the inductive step.
  • So by induction they can all find a marriage partner and live happily ever after.

Which of these statements is difficult to follow?

  • 0
    It is not difficult to understand the sentense,the point is ,is it always works? As the man who the girl know can be randomly chosen,what if a case there is only one distributing way to distribute the man among the woman?Is this method work too and is there any proof about this method?2012-02-08
  • 0
    @Mathematics: If there is only one way to reallocate the $m+1$ girls and boys into engaged pairs, this would mean that each boy at the party only received one invitation, and when choosing dancing partners each boy would only have one choice, but the method would still work. It will always work based on the supposition in the question.2012-02-08
0

Here are some basic concepts that may help. Relations are not always transitive, which is why we talk about closures. Connectivity in graph theory is also relevant.