shadock a écrit:

Si on prend un groupe de 6 personnes, il est évident que soit au minimum trois personnes se connaissent ou soit au minimum trois ne se connaissent pas.

Hummm, pourquoi ? J'ai déjà du mal avec le postulat de départ.

Hmmm c'est pas évident. Chaque personne peut connaître une seule et unique autre personne. Dans ce cas, chaque personne connaît au moins quelqu'un d'autre, mais elle ne connait pas forcément tout le monde.

A connait B qui connait C qui connait D ... E ... F.

Mais A ne connait ni C ni D ni E ni F.

Non, dans la chaine de quaramba, B connait A et C mais C ne connait pas forcement A, donc ils ne se connaissent pas forcement.

Après dire que dans un groupe de 6 personnes (avec un système de parrainage par exemple) il y a forcement au moins une personne qui en connait deux autres, oui, mais ILS ne se connaissent pas forcement.

J'ai peut-être zappé un truc.

PS : Je suis membre de FPNPS (Front de Promotion des Nombres Premiers Sexy) et soit je suis seul, soit personne ne se connait au sein de ce groupe.

Comme Seanbateman, j'ai du mal avec le postulat de départ, car je pourrai tout aussi bien écrire:

Si on prend un groupe de 6 personnes, il est évident que soit au minimum deux personnes se connaissent ou soit au minimum deux ne se connaissent pas.
Admettons maintenant une fonction qui à un nombre [latex]n[/latex] de personnes dans un groupe [latex]G[/latex] nous donne le nombre de personne minimal qui se connaissent ou non.

Pour mon exemple on a [latex]G(6)=2[/latex]
...

Sinon, je pense pas que tu aies pris la lettre [latex]G[/latex] au hasard, car cela sonne comme de la théorie des graphes.

Est-ce que par "[latex]n[/latex] personnes se connaissent", tu voudrais dire un sous-graphe complet de taille [latex]n[/latex]?

Je connais ce problème. C'est pour un groupe se connaitre mutuellement ou ne pas se connaitre du tout.
On a bien dans un groupe de 6 personnes 3 qui se connaissent mutuellement ou 3 qui se connaissent pas du tout.

oui r(3,3)=6.

Le postulat est assez peu clair mais vrai.

Si personne ne connait personne : 6 personnes ne se connaissent pas donc au moins 3
Si deux personnes seulement se connaissent,  4 ne se connaissent pas.
Si ils se connaissent deux à deux , 3 personnes tirées de chaque couple ne se connaissent pas.
Si trois personnes se connaissent, c'est au moins 3.

Il faut donc pour G(n)=3 , un nombre (n-1)^2+1 = 5 personnes
G(n) = 4 sera atteint pour n= 3^2+ 1 = 10 personnes je pense.
A 9 on peut encore faire 3 groupes de 3

G(n) = 1     n=1
G(n) = 2     n=2 à 4
G(n) =3      n=5 à 9
G(n) = 4     n=10 à 16
G(n) = 5     n=17 à 25
G(n) =6      n=26 à 36
...

G(n)  pourrait être ent (rac(n-1)) +1

Je fais la réponse à ma propre réponse: 3 groupe de 3 , ça fait déjà un paquet de personnes qui ne se connaissent pas 2 à 2. Donc c'est plus compliqué que ça ...

shadock a écrit:

Si on prend un groupe de 6 personnes, il est évident que soit au minimum trois personnes se connaissent ou soit au minimum trois ne se connaissent pas.

Ce n'est pas évident du tout pour moi.
Quelqu'un connaît une démonstration expéditive ?
shadock ?

oki merci.