Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
There are 2n people at a hotel. Each person knows exactly n other people. Prove they can be paired up...?
There are 2n people at a hotel where n is a postive integer. Each person knows exactly n other people. Prove that they can be paired up and assigned to rooms so that everyone knows his/her roommate.
Note: The knowing relation is mutual so A knows B implies B knows A
I was hoping there was an easier proof, but if that indeed isn't the case then I'll give A Cave the points.
2 réponses
- il y a 1 décennieRéponse favorite
This is a particular case of the Marriage theorem (or Hall's theorem we call it).
[I really don't know what else to put into the answer for such topics which pose well-known questions.]
Ok, here is the link: http://en.wikipedia.org/wiki/Marriage_theorem
Watch the paragraph about graph theory. The inequality | X | <= | N(X) | is held quite obviously with your conditions.
As far as I remember there is no much easier proof of this fact.
- MathMan TGLv 7il y a 1 décennie
[ oops - my nifty algorithm didn't work ... back to the drawing board ]