![](/img/vague-bas-gauche.png) |
#1 - 28-05-2011 13:54:05
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Nombre de personne qui se connaisseent ou non dans un groupe.
Cela fait plusieurs mois que je me pose une question.
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. 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)=3[/latex] Peut-on trouver [latex]n[/latex] pour que [latex]G(n)=4[/latex] et est-il possible de définir une telle fonction pour tout [latex]n[/latex]?
NB: Je n'en ai pas fait une énigme mathématique car je n'ai aucune idée du niveau qu'il faut pour répondre à cette question qui parait si simple.
Amicalement, Shadock ![smile](img/smilies/smile.png)
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#2 - 28-05-2011 14:55:26
- quaramba
- Sage de Prise2Tête
- Enigmes résolues : 47
- Messages : 1538
- Lieu: Entre une chaise et un bureau
nombre de personne qui se connaissent ou non dans yn groupe.
J'ai rien compris ![neutral](img/smilies/neutral.png)
脱了裤子放屁
#3 - 28-05-2011 15:46:28
- Seanbateman
- Professionnel de Prise2Tete
- Enigmes résolues : 21
- Messages : 321
- Lieu: Toujours à l'énigme 3
Nombre de personne qui se conaissent ou non dans un groupe.
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.
Quand on ne sait rien, on peut tout de même trouver des choses, avec de l'imagination. [Boris Vian]
#4 - 28-05-2011 16:07:51
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Nombre de personnee qui se connaissent ou non dans un groupe.
Bah imagine un groupe de six personnes si 1 personne ne connais personnes il y en a 5 qui se connaissent. 2 personnes ne se connaissent pas il y en a 4 qui se connaissent. 3 personnes ne se connaissent pas il y en a 3 qui se connaissent. Etc... donc dans un groupe de six personnes il y a au moins 3 personnes qui se connaissent ou au moins trois personnes qui ne se connaissent pas.
![smile](img/smilies/smile.png)
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#5 - 28-05-2011 16:19:45
- quaramba
- Sage de Prise2Tête
- Enigmes résolues : 47
- Messages : 1538
- Lieu: Entre une chaise et un bureau
Nombre de personne qui se connaissent ou non danss un groupe.
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.
脱了裤子放屁
#6 - 28-05-2011 16:49:27
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
nombre de personne qui se connaiqsent ou non dans un groupe.
Et donc au moins 3 personnes se connaissent.
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#7 - 28-05-2011 17:26:01
- Seanbateman
- Professionnel de Prise2Tete
- Enigmes résolues : 21
- Messages : 321
- Lieu: Toujours à l'énigme 3
nombre de personne qui se connaissent ou non dans un griupe.
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.
Quand on ne sait rien, on peut tout de même trouver des choses, avec de l'imagination. [Boris Vian]
#8 - 28-05-2011 17:33:53
- quaramba
- Sage de Prise2Tête
- Enigmes résolues : 47
- Messages : 1538
- Lieu: Entre une chaise et un bureau
Nombre de personne qui se connaissent ou nn dans un groupe.
脱了裤子放屁
#9 - 28-05-2011 18:50:44
- Kikuchi
- Passionné de Prise2Tete
- Enigmes résolues : 46
- Messages : 91
nombre de perspnne qui se connaissent ou non dans un 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]?
There's no scientific consensus that life is important
#10 - 28-05-2011 18:53:21
- irmo322
- Professionnel de Prise2Tete
- Enigmes résolues : 36
- Messages : 203
nimbre de personne qui se connaissent ou non dans un groupe.
Tu peux préciser un peu la relation "connaitre quelqu'un"? Par exemple si A connait B et B connait C, alors est-ce que ça implique que A connait C? (C'est faux dans la vie courante) Si A connait B, alors est-ce que B connait A? (Par exemple, si une star vient dans une soirée, tout le monde la connait mais elle ne connait pas tout le monde)
Avec ça, j'aurais plus d'éléments pour te répondre.
#11 - 28-05-2011 19:34:07
- Yanyan
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 509
- Lieu: Lille si j'y suis
nombre de personne qui se connaissent oi non dans un groupe.
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.
Un mathématicien complet est topologiquement fermé!
#12 - 28-05-2011 19:47:15
- Seanbateman
- Professionnel de Prise2Tete
- Enigmes résolues : 21
- Messages : 321
- Lieu: Toujours à l'énigme 3
nombre de personne qui se connaissebt ou non dans un groupe.
Je suis perdu là, un rapport avec les nombres de Ramsey ?
Quand on ne sait rien, on peut tout de même trouver des choses, avec de l'imagination. [Boris Vian]
#13 - 28-05-2011 19:54:01
- Yanyan
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 509
- Lieu: Lille si j'y suis
Nombre de personne qui se connaissent ou non dans un groupe
Un mathématicien complet est topologiquement fermé!
#14 - 28-05-2011 20:03:46
- Seanbateman
- Professionnel de Prise2Tete
- Enigmes résolues : 21
- Messages : 321
- Lieu: Toujours à l'énigme 3
Nombre de personne qui se connaissent ou non dans un rgoupe.
Ok, mais l'énoncé était falacieux
Quand on ne sait rien, on peut tout de même trouver des choses, avec de l'imagination. [Boris Vian]
#15 - 28-05-2011 20:51:00
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
nombre de personne qui se connaissent ou non sans un groupe.
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
#16 - 28-05-2011 20:56:49
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Nombre dee personne qui se connaissent ou non dans un groupe.
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.
![smile](img/smilies/smile.png)
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#17 - 28-05-2011 21:11:55
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
nombre de personne qui sz connaissent ou non dans un groupe.
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 ...
#18 - 28-05-2011 21:28:00
- SHTF47
- Imprnnçbl de Prs2Tt
- Enigmes résolues : 39
- Messages : 1629
- Lieu: Autre nom du colin
Nombre de personne qui se connaissent ou non dans un group.e
Socrate a dit:
CONNAIS TOI TOI-MEME
Si ça peut vous aider... ![wink](img/smilies/wink.png)
La musique est une mathématique sonore, la mathématique une musique silencieuse. [Edouard HERRIOT]
#19 - 29-05-2011 18:57:07
- ash00
- Sage de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,925E+3
Nombre ed personne qui se connaissent ou non dans un groupe.
#20 - 03-06-2011 11:25:38
- Yanyan
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 509
- Lieu: Lille si j'y suis
nombre de personne qui se connaidsent ou non dans un groupe.
R(4,4)=18 donc la réponse est, semble-t-il, 18.
Un mathématicien complet est topologiquement fermé!
#21 - 06-11-2012 23:08:22
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
nombre de perspnne qui se connaissent ou non dans un groupe.
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 ?
#22 - 06-11-2012 23:37:02
- irmo322
- Professionnel de Prise2Tete
- Enigmes résolues : 36
- Messages : 203
Nombre de personne qui se connnaissent ou non dans un groupe.
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
#23 - 07-11-2012 00:04:54
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Nombre d personne qui se connaissent ou non dans un groupe.
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |