Combinatoire

[hervedo]

Bonsoir à tous,

J ai une petite question...je pars du lemme des poignées de main. Je prends n personnes qui se serrent la main, j ai donc n(n-1)/2 poignées de main, je représente tout ça avec un graphe complet. Si deux personnes s apprécient je colorie l arête en bleu sinon je la colorie en rouge. Je viens de m apercevoir qu à partir de n=6 je suis obligé d avoir au moins un triangle colorié avec 3 arêtes rouge ou bleu. Je me dis que c est certainement parce qu à partir de n=6 j ai plus de triangles que d arêtes...mais je n ai pas d argument plus convaincant. Est-ce que quelqu un a une idée ? Merci.

[Ben314]

Salut,
C'est pas bien compliqué (et c'est bien connu) : Tu prend un sommet quelconque, il en part 5 arrêtes donc forcément (au moins) 3 de la même couleur, y'a qu'à dire rouge par exemple. On regarde ensuite les 3 sommets situés à l'autre bout de ces trois arrêtes rouges. Si parmi les 3 arêtes reliant ces 3 sommets il y en a une rouge, ben ça fait un triangle rouge et si y'en a pas, c'est qu'on a sous les yeux un triangle bleu.

[hervedo]

Salut,

Oups désolé ma question était idiote...je cherchais un argument purement "calculatoire" désolé...

Merci.