Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 28-05-2011 13:54:05

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Nombre de personne qui see connaissent 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


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
  • |
  • Répondre

#0 Pub

 #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 quo se connaissent ou non dans un groupe.

J'ai rien compris neutral


脱了裤子放屁

 #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 connaissent ou non dans un gtoupe.

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 personne qui se connaissent ou non dans un geoupe.

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


"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 connaisesnt ou non dans 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 coonnaissent 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 conniassent ou non dans un groupe.

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 non dans n groupe.

Voui moi aussi


脱了裤子放屁

 #9 - 28-05-2011 18:50:44

Kikuchi
Passionné de Prise2Tete
Enigmes résolues : 46
Messages : 91

Nomber de personne 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

Nombre de personne qui se connaissent ou non dans un gorupe.

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 persobne qui se connaissent ou 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 personnne qui se connaissent 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 connaissetn ou non dans un groupe.

oui r(3,3)=6.


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 connaisent ou non dans un groupe.

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 : 6,004E+3

Nombre de personne qui se connaissent ouu non dans 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 de personne qui se connaissent ou non dzns 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


"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 : 6,004E+3

Nombre de personne qui se conniassent 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 ggroupe.

Socrate a dit:

CONNAIS TOI TOI-MEME


Si ça peut vous aider... wink


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,930E+3

Nombre de personne qui se connaissent ou non danns un groupe.

lol

 #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 see connaissent 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 personne qui se connaissent ou non sans 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 connaissent ou nin 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.

oki merci.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
16-02-2012 Blabla
P2T
Bonne année 2011 par EfCeBa
01-01-2011 Blabla
P2T
06-09-2011 Blabla
31-12-2009 Blabla
16-07-2013 Blabla
11-05-2009 Blabla
P2T
Rappel à l'ordre par ash00
23-09-2015 Blabla
P2T
Forum Schmilblick par swoop
01-08-2008 Blabla
P2T
Bonjour par RanchoMontpellier
31-10-2012 Blabla

Mots clés des moteurs de recherche

Mot clé (occurences)
Trois personnes se connaissent mutuellement dans un groupe de 6personnes (2) — Deux personnes qui se connaissent (2) — 3 personnes se connaissent graphe (2) — Dans une fete il y a au moins 6 personnes montrer que 6 personnes se connaissent (2) — 3 personnes qui se connaissent (2) — Regle connait 10 personnes qui connaissent 10 personnes (2) — Entre 6 personnes ya au moins 3 qui se connaissent mutuellement ou 3 qui se connaissent pas du tout (2) — Ungroupe de personne qui semble pas se conetre mais qui se conesse tres bien (2) — Combien de personnes nous connaissent (2) — Deux personnes qui se connaisse (2) — Groupe de six personnes (2) — Graphe montrer que dans tout groupe de 6 personnes 3 personnes se connaissent (2) — Groupe 6 personnes 3 se connaissent (2) — Graphe groupe de 6 personnes 3 se connaissent (2) — 6 personnes qui se connaissent (1) — Personne se connaissait (1) — Deux personnes qui connaisse (1) — Nombrecde personnes qui se connaissent dans le monde (1) — Deux personnes se connaissent (1) — Groupe combien de personnes 2 (1) — Nombres de personne (1) — 6 personnes se connaissent problemes maths (1) — Demonstration dans un groupe de 6 personnes 3 personnes se connaissent (1) — Dans un groupe de 6 personnes (1) — Theorie sur deux personnes connaissent une celebrite (1) — Theorie des graphes 6 personnes se connaissent (1) — Six personnes connaissent six personnes (1) — Personnes qui connaissent une autre personne (1) — Deux personnes qui se connaissent ce groupe (1) — 2 personnes qui se connaissent (1) — Personne qui connaissent (1) — Une question personne ne connaisent (1) — 2 personnes qui connaissent (1) — Comme deux personnes qui se connaissent (1) — Montrer que dans un ensemble de six personnes soit il en existe trois qui se connaissent soit il en existe trois qui ne se connaissent pas (1) — Persone a deux tete (1) — Trois personnes qui se connaissent (1) — Nombre de personnes qui se connaissent dans le monde (1) — Combien de personne on connait (1) — Soiree 6 personnes 3 se connaissent (1) — Deux personnes qui connaissent (1) — Question pour savoir si deux personnes se connaissent (1) — Il y en a qui se connaisse mal (1) — Cercle de personnes qui connaissent tout le monde (1) — Dans un groupe de 6 personnes 3 se conaissent graphes (1) — Moins de sept personnes se connaissent (1) — 3 personne se connaisse mutuellement alors 3 ne se connaisse pas theorie (1) — Comment dire deux personne qui se connaissent bien (1) — Deux personne qui se conaisse (1) — Montrer que parmi six personnes quelconqueil existe un groupe de 3 personnes qui se connaissent mutuellement (1) — Combien de personnes entre deux qui ne ce connaissent pas? (1) — 6 personnes se conaissent (1) — Personnes que se connaissent (1) — 6 personnes se connaissent (1) — Combien de personne entre 2 personnes dans le monde (1) — Combien yat-il de personne qui travail a la tan (1) — Discussion entre deux personnes qui ne se connaisse pas (1) — Combien de personnes te connaissent ? (1) — Graphe montrer qu il existe au moins n-3 personnes qui conaissent tout le monde (1) — 3 groupes de personnes avec le meme nombre (1) — 6 personnes qui connaissent 6 personnes (1) — Il y a soit trois personne qui se connaissent deux a deux soit (1) — 2 personnes qui connaissent une personne (1) — 3 personnes se connaissent mutuellement 3 personne ne se connaissent pas (1) — Dans un groupe de personne qui se connaisse deja (1) — 6 personnes 3 se connaissent 3 ne se connaissent pas (1) — 3 personnes qui se connait mutuellement (1) — 6 personne forcement trois personnes qui se connaisse (1) — Il ya des gens qui connaissent meme pas deux (1) — En combien de personnes on connait tout le monde (1) — 6 personnes ne se connaissent pas ou se connaissent (1) — 1 personne sur 6 se connaisse dans le monde (1) — Personne se connaisse a personne +6 (1) — Deux personne qui ne se connaisait pas (1) — Combien+de+personnes+dans+un+groupe+pour+que+2+se+connaissent (1) — Personne qui se connaissent (1) — Pour un groupe de six personnes (1) — Quand on ne sait rien on peut tout de meme trouver des choses avec de l?imagination. (1) — Le fait que des personnes se connaissent (1) — 2 personnes sur 6 se connaissent (1) — 3 personnes qui connaissaient (1) — Loi des 5 personne qui se connaissent (1) — Six personnes qui connaissent six personnes (1) — 6 personnes 3 se connaissent (1) — Combien de personne minimum dans un groupe (1) — Dans un groupe de 6 personnes il y a toujours 3 personnes qui se connaisse ou trois qui ne se conaissent pas (1) — Nombre de personne qui se connaissent (1) — Groupe de six personns (1) — Nombre de personnes qui se connaissent (1) — Si 3 personnes se connaissent (1) — Montrer que dans un graph de ix personnes qui se connaissent mutuellement que cela n est pas (1) — Tout groupe d au moins 6 personne (1) — Six personnes connaisent tous le monde (1) — Cinq personnes se connaissent (1) — Dans un groupes de 6 personnes il y a toujours 3 personnes qui se connaissent mutuellement et 3 qui ne se connaissent pas (1) — Combien de personnes connaissent la (1) — Groupe de personne nombre de personne minimum (1) — Quand on ne sait rien on peut tout de meme trouver des choses avec de l imagination (1) — 6 personnes deux se connaissent (1) — 2 personnes qui ne se connaissent pas (1) — Deux personnes au hasard se connaissent (1) — Combien de personnes me connaissent (1) — Connaitre personnes qui connaissent personnes (1) — Enigme que personne connait (1) — Statistique dans un groupe de personnes au moins deux se connaissent (1) — Entre personne a et personne b 5 personnes qui se connaissent (1) — 5 personnes se connaisse (1) — Dans un groupe de 6 personnes 3 personne se connaissent ou 3 ne se conaisse pas (1) — Combien de personnes connaissent des personnes que je connais (1) — 3 personnes se connaissent mutuellement theorie de graphe solution (1) — Nombre minimum personnes 3 au moins se connaissent ou se connaissent pas (1) — Pour me montrer il faut bien me connaitre (1) — Combien de personne jeux en ligne (1) — Combien de gens connait on (1) — Tous ce que les personnes se connaient (1) — Il y a au moins deux personnes qui connaissent (1) — Si on prend un groupe de 6 personnes (1) — Combien de personnes connaissent le basik (1) — Nombre de personne qui se connaisse dans le monde (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete