Les poignées de mains des invités



Problème
Lors d'une soirée, les invités ont tous serré la main de trois autres invités, excepté l'un d'entre eux qui n'a donné qu'une seule poignées de mains.

Il s'agit avec ces seules informations de répondre aux questions suivantes :

Quel est le plus petit nombre d'invités, possible de cette soirée ?
Peut-il y avoir dix-neuf invités ?
Peut-on avoir n'importe quel nombre d'invités au-delà d'un certain minimum ?
-Si oui pourquoi ?
-Sinon indiquer les nombres possibles.



SOLUTION

Le plus petit nombre de personnes, possible est six.

-En effet, de façon évidente, trois ou moins de trois n'est pas possible.

-Quatre n'est pas possible car si trois personnes serrent la main des trois autres, le quatrième aura obligatoirement serré la main des trois autres.

-Cinq n'est pas possible, en effet chacun des quatre invités donnant trois poignées de mains, le cinquième en donnera ou zéro ou deux
.


Six est possible.
Nommons les invités A, B, C, D, E et F.
Voici une configuration possible des poignées de mains :
A <-> B
B <-> C
C <-> D
D <-> E
E <-> F
A <-> C
A <-> E
B <-> D

 

Dans ce cas, F échange une seule poignée de mains avec E.


 

Il ne peut y avoir dix-neuf invités car le nombre de personnes doit être pair.
En effet, chaque fois qu'un invité X échange une poignée de mains avec Y, alors Y échange une poignée de mains avec lui. Le nombre de poignées de mains augmente donc de deux et non pas de un.
Le nombre de poignées de mains est pair car échangé entre deux personnes, donc compté deux fois.
Si les invités étaient au nombre de dix-neuf, le nombre total de poignées de mains échangées serait de 18*3 +1 = 55.
C'est impossible car 55 est impair.
De façon génrale s'il y a (2n+1) personnes (nombre impair), le nombre de poignées de mains est 2n *3 +1 = 6*n +1.
Et 6*n + 1 est imapir d'où impossibilité dans le cas général.

A partir de six, tout nombre multiple de quatre fonctionne.


Huit fonctionne
Choisissons les invités : A, B, C, D, E, F, G, H :
A <-> B
B <-> C
C <-> D
D <-> E
E <-> F
F <-> G
G<-> H

A <-> C
A <-> E
B <-> G
D <-> F


Et chaque groupe, de quatre invités, supplémentaire peut fonctionner en circuit fermé :
par exemple, chaque personne de ce dernier groupe ne donne une poignée de mains qu'à une personne de ce groupe de quatre.
Ainsi tous donnent trois poignées de mains sauf l'une des personnes du premier groupe de six ( Voir le premier schéma de la question ), il s'agit de l'invité nommé H.

 


Menu trucs   Accueil