Un bon repas

Olympiades mathématiques, énigmes et défis
raptor77
Membre Rationnel
Messages: 813
Enregistré le: 27 Mai 2006, 06:48

un bon repas

par raptor77 » 15 Juil 2006, 13:08

Bonjour voici un exo d'olympiade
Lors d'un repas se réunissent 2N personnes. Chacune connaît au moins N des autres personnes présentes.

Prouver que l'on peut choisir quatre de ces personnes et les placer autour d'une table ronde de sorte que chacune connaisse ses deux voisins.

(On considère que « se connaître » est une relation réciproque.)

Bonne chance
Cordialement
Raptor
ps: aviateur a toi de jouer



BancH
Membre Irrationnel
Messages: 1317
Enregistré le: 17 Mar 2006, 21:50

par BancH » 15 Juil 2006, 13:44

Dans le pire des cas, chaque personne connaît exactement autres personnes.

et sont deux personnes distinctes. Si l'on admet qu'elles ne se connaissent pas, alors et appartiennent à deux groupes de personnes différents.

Si quatre personnes ne peuvent pas être disposées en cercle de façon à ce que chaque personne connaisse ses voisins, il n'y aurait que deux groupes.
Soit le groupe de composé donc de personnes. Parmis toutes les personnes se connaissent entre elles.

est le groupe de composé aussi d'au moins personnes.



Il y a deux personnes qui appartiennent aux deux groupes, il est donc impossible de séparer les personnes en deux groupes de telle sorte qu'aucune personne d'un groupe connaisse une personne de l'autre groupe.
Il y aura alors au minimum deux personnes qui appartiennent aux deux groupes.

Soit et ces deux personnes.

Alors, connaît qui connaît qui connaît qui connaît .

aviateurpilot
Membre Irrationnel
Messages: 1772
Enregistré le: 01 Juin 2006, 21:33

par aviateurpilot » 16 Juil 2006, 13:23

=> on suppose de tous les presonnes se connaissent
alors on prend au hazard presonnes (ils verifient la solution )

=>sinon, il existent 2 presonnes qui ne se connaissent pas.
1er personne connais au moin n personne parmi les 2n-2 restant.=A
2eme personne connais au moin n personne parmi les 2n-2 restant.=B
card(A\cap B))=cardA+cardB-card(A\cup B)\le n+n-(2n-2)=2
alors il existe une 3eme personne qui connai la 1er et la 2eme personne
et une 4eme personne qui connai la 1er et la 2eme personne
et voia la table:
_______3eme p
1er p (la table) 2emep
_______4eme p

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 111 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite