|
Résumé de la discussion
- titoufred
- 07-11-2012 00:04:54
- irmo322
- 06-11-2012 23:37:02
La relation "se connaitre" est ici réflexive.
Une démonstration adaptée de wikipedia:
Parmi les 6 personnes, je prends Alice.
1er cas: je suppose que Alice connait 3 autres personnes que je nomme Bob, Charlie et Denis. Deux sous-cas: - Bob, Charlie et Denis ne se connaissent pas et alors il forment un groupe de 3 personnes ne se connaissant pas. - Bob et Charlie se connaissent (resp "B et D se connaissent" ou "C et D se connaissent"), alors le trio Alice, Bob et Charlie (resp A, B et D ou A, C et D) se connaissent. -> 1er cas réglé.
2ème cas: On suppose que Alice ne connait pas trois autres personnes. Un raisonnement similaire nous mène au même résultat (il suffit de remplacer les "ne se connaisse pas" par "se connaisse" et inversement.
Source: http://en.wikipedia.org/wiki/Ramsey%27s_theorem
- titoufred
- 06-11-2012 23:08:22
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 ?
- Yanyan
- 03-06-2011 11:25:38
R(4,4)=18 donc la réponse est, semble-t-il, 18.
- ash00
- 29-05-2011 18:57:07
- SHTF47
- 28-05-2011 21:28:00
Socrate a dit:
CONNAIS TOI TOI-MEME
Si ça peut vous aider...
- gwen27
- 28-05-2011 21:11:55
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
- 28-05-2011 20:56:49
Excusez moi si j'ai été peu clair, et un sous-graphe complet de taille n je ne sais même pas ce que sais. Quant au G je l'ai pris pour Groupe c'est tout.
- gwen27
- 28-05-2011 20:51:00
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
- Seanbateman
- 28-05-2011 20:03:46
Ok, mais l'énoncé était falacieux
|
|
Prise2Tete
Forum
Statistiques
Liste des membres
Hall of Fame
Contact
|