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 : 3332

nombre de personne qui de 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



Annonces sponsorisées :

"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 qui se connaisssent 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 uo 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 : 3332

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


"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

Nomre de personne qui se connaissent 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 : 3332

Nombre de ppersonne qui se connaissent 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 connnaissent 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 ersonne qui se connaissent ou non dans un groupe.

Voui moi aussi


脱了裤子放屁

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

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

Nombre de peronne 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 persoonne 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

NNombre de personne 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 pesronne 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

Noombre de personne qui se connaissent 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 qu se connaissent 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 : 5,679E+3

Nombre de personne qui se connaissent ou 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 : 3332

Nombr de 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


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

Nombre de personne qui se connaissnt 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 oi non dans un groupe.

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

nombre de perspnne qui se connaissent ou non dans 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 se connaissent ou non dans n 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 : 1746

Nombre de personne qui se cnonaissent 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 connaissent ou non dans in 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 : 1746

Nombre de personne qui se connaisseent 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 : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
16-02-2012 Blabla
P2T
Merci par cheyenneveritas
07-05-2011 Blabla
25-08-2010 Blabla
P2T
St Valentin 9.3 par maïtou22
14-02-2009 Blabla
P2T
Hommage et Pépite par HAMEL
28-06-2009 Blabla
05-08-2008 Blabla
15-01-2010 Blabla
P2T
Un dîner presque P2T. par FRiZMOUT
30-06-2010 Blabla
P2T
Mdna par NickoGecko
27-03-2012 Blabla

Mots clés des moteurs de recherche

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