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 - 04-07-2011 12:19:31

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Toutes mes amitiéés (+ questions subsidiaires)

Je ne pense pas qu'il soit bien dur de trouver une solution, mais je veux bien voir vos raisonnements, voire vos preuves si vous en trouvez.

Dans une assemblée de N personnes, on sait que chaque personne en connaît p autres. Combien peut-on rassembler de personnes qui ne se connaissent pas du tout ?

EDIT 5 juillet, 17h35 :

Je précise, pour Clydevil notamment, que :
- "se connaître" est supposé être une relation symétrique (mais la symétrie n'est probablement pas indispensable pour trouver le plus grand nombre d'inconnus que l'on peut rassembler... pour la question subsidiaire, probablement).
- quand je dis "chaque personne en connaît p autres", ça veut dire qu'elle en connaît effectivement p autres, ni plus ni moins (ça a l'air bête, mais bon...)

Et, euh, ah oui ! la question subsidiaire (soufflée par Frank) :

Dans le "pire des cas" (à savoir les liens d'amitié qui "nous arrangent le moins", combien de personnes peut-on rassembler qui ne se connaissent pas ?

La réponse 0 est refusée d'office, ne serait-ce que parce qu'en isolant une personne, on obtient un sous-ensemble de la population de départ dans lequel on ne peut pas trouver deux personnes qui se connaissent. Donc 1 est un minorant de la réponse attendue smile

Je précise aussi, suite à une remarque de Clydevil (encore lui), que n'importe quelle couple (N,p) ne peut pas être possible, ce qui m'amène à une deuxième question subsidiaire :

Comment caractériser les couples (N,p) tels qu'il est possible que chacune des N personnes en connaisse exactement p autres, sachant que la relation "se connaître" est symétrique ("si je connais quelqu'un, il me connait, et vice-versa") ?

Je n'ai pas encore vraiment réfléchi à ces deux questions. A vue d'œil, je tenterais d'utiliser de la théorie des graphes pour la première, et de la combinatoire pour la deuxième, mais je ne peux pas dire que je suis sûr de moi...



Annonces sponsorisées :

Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
  • |
  • Répondre

#0 Pub

 #2 - 04-07-2011 14:09:03

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2714
Lieu: Luxembourg

Tooutes mes amitiés (+ questions subsidiaires)

Bonjour,

Dans le meilleur des cas, il pourrait se former des sous-groupes de p+1 personnes qui se connaissent toutes entre elles. On aurait alors ent(N/(p+1)) groupes indépendants. Tout rassemblement constitué d'une personnes de chacun des sous-groupes répond à la question. Donc réponse: ent(N/(p+1)).

Dans le pire des cas, comme la relation "connaitre une autres parsonne" n'est ni transitive ni forcémént symétrique, aucun rassemblement ne répondrait à la question: par exemple si toutes les personnes étaient assises à une table ronde en connaissant ses deux voisins. Et donc réponse: 0.

Bonne journée.
Frank

Edit: je ne suis plus sûr de mon raisonnement dans le "pire des cas", car dans ce cas un sous-groupe constitué d'une personne sur trois autour de la table répondrait à la question. Donc en fait je ne sais plus rien, mais je vais réfléchir encore.

 #3 - 04-07-2011 14:26:05

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

Toutess mes amitiés (+ questions subsidiaires)

Salut,
J'imagine que:
-c'est "exactement" p autre.
-connaitre quelqu'un est ici une relation symetrique. (tu dis "se connaitre" donc ca semble naturel)
Si oui c'est rigolo mais je n'avais jamais remarqué que parfois ce n'était pas possible. (ie s'il y a 3 personnes elles ne peuvent pas chacune en connaitre exactement une)

 #4 - 04-07-2011 15:20:08

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

Toutes mes amitiés (+ questions ssubsidiaires)

Je pense qu'il faut raisonner avec nombres pairs et nombres impairs mais là j'ai pas le temps d'ici là j'espère trouver une réponse convenable.

Premières pensées à la rache :
Une réponse qui me parait évidente au départ ne l'ai pas forcement, mais je pense que si [latex]X[/latex] est le nombre de personne qui ne se connaissent pas alors [latex]X=(N-p)[/latex]
Par exemple dans une assemblée [latex]N=7[/latex] et [latex]p=6[/latex] alors il y a deux personnes qui ne se connaissent pas puisque chacune en connais 6 parmi 7.
Donc en appliquant la formule sa me donne [latex]X=(N-p)=(7-6)=1[/latex].
Si on essaye avec [latex]p=3[/latex] on a [latex]X=4[/latex] ce qui semble fonctionner mais je pense que pour ce genre de problème quelques connaissances plus approfondie sur les ensembles ne sont pas de trop, parce qu'une "démonstration" s'appuyant sûr deux exemples c'est bof sad
De plus un de mes deux exemple est faux puisque [latex]1=2[/latex] ça fait bizarre lol

Avec plus de finesse et de réflexion :

1) Soit [latex]N_p[/latex] une assemblée dont le nombre de personne est pair.
2) Soit [latex]N_i[/latex] une assemblée dont le nombre de personne est impair.

Cas No.1 :
Si dans une assemblée le nombre de est pair, et que [latex]p[/latex] c'est aussi alors soit deux personnes ne se connaissent pas, soit un ne connait personne ( sauf lui même et donc tout le monde se connait franchement tu te poses de ces questions !! lol ).

Démonstration : Soit [latex]p[/latex] le plus petit des nombres pairs différent de zéro donc [latex]p=2[/latex] pour maximiser le nombre de personnes qui ne se connaissent pas.
Première possibilité tout le monde se connait sauf deux : si A et B connaissent {C;D} alors A et B ne se connaissent pas. Si l'assemblée est plus grandes on a [latex]X=N-2[/latex]
Deuxième possibilité, il en reste un si [latex]p=1[/latex] (le minimum pour maximiser)

Cas No.2
Si dans une assemblée il y a un nombre impair de personne c'est le même raisonnement que précédemment enfin je crois hmm
Shadock


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

 #5 - 04-07-2011 16:06:59

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

Toutes mes amiiés (+ questions subsidiaires)

Je suppose que si A connait B, B connait A.
De plus le nombre maximum dépend de la relation de connaissance elle-même et que donc on cherche justement l'organisation du groupe qui permet d'obtenir le plus grand nombre.

Dans ce cas, je pense que le maximum est atteint lorsque l'organisation est la suivante:
Je fais des groupes de p personnes.
Je regroupe ces groupes par paire. Chaque personne du premier groupe connait chaque personne du deuxième groupe de la paire.
Chacun connait bien p personnes (dans l'autre groupe) mais ne connait personne de son groupe. Ces p personnes ne se connaissent pas entre elles ni ne connaissent quelqu'un d'un groupe d'une autre paire.
On peut donc choisir un groupe de p personnes par paire.

Donc si N=2kp, on peut avec cette disposition choisir kp (N/2) personnes qui ne se connaissent pas.
Il reste le cas du reste de la division de N par 2p à traiter.
Je vais essayer d'y réfléchir plus.
(Il doit y avoir un rapport avec les graphes bipartites bicolores mais je ne vois pas trop quel résultat utiliser)...

 #6 - 04-07-2011 16:09:01

kosmogol
Banni
Enigmes résolues : 49
Messages : 11,928E+3

Toutes mes amiiés (+ questions subsidiaires)

je m'occupe des cas aux limites
p=0 réponse N
p>=N réponse 0

entre les deux, je le laisses le soin aux matheux de répondre.


http://enigmusique.blogspot.com/

 #7 - 05-07-2011 17:31:02

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

toutes mes amitiés (+ qiestions subsidiaires)

En plus du "UP", je rajoute quelques remarques qui introduisent deux questions subsidiaires. Je vais ajouter 24 heures et me casser la tête avec vous big_smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #8 - 06-07-2011 10:32:52

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Toutes mes amitiés (+ questions sbusidiaires)

Les couples N, p possibles sont ceux où au moins n ou p est pair.

Il faut constituer N*p/2 couples de relations symétriques, donc si n et p sont impairs, ce n'est pas possible.

Sinon, on prend N personnes qui ne se connaissent pas.
Tant qu'il existe des personnes qui connaissent strictement moins de p personnes, on fait faire connaissance aux 2 personnes qui connaissent le moins de personnes.
Le nombre total de relation augmente de 2 à chaque étape. Et le nombre de relation par personne augmente au plus de 1 à chaque étape. Chaque personne finira par connaître exactement p personnes.

edit : arf c'est faux, les 2 personnes se connaissent peut être déjà ><

 #9 - 06-07-2011 10:54:40

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1433

Toutes mes amitiés (+ question ssubsidiaires)

Petites réflexions sur le sujet (je chercherai plus en détail ce soir)

Si N et p sont impairs, alors un tel groupe ne peut pas exister.
En effet, on représente tout ça par un graphe; le nombre d'arêtes est N.p/2 (chaque personne en connait p, donc N.p; mais chaque relation étant réciproque elle est comptée deux fois)

Pour la suite je parle à chaque fois du cas optimal
Pour p=0 la réponse est N
Pour p=1 la réponse est N/2 (pour N pair)
Pour p=2 la réponse est E(N/2). Dans un cas non optimal on peut descendre jusqu'à N/3 dans les cas où N est un multiple de 3
Pour p=Pi > Pj la réponse optimale est nécessairement inférieure ou égale à celle de Pj (puisque sinon, en enlevant des arêtes de la solution Pi on ne crée pas de nouvelle connaissances donc la réponse serait alors applicable à Pj aussi)

 #10 - 06-07-2011 16:53:39

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 808
Lieu: Seahaven island

toytes mes amitiés (+ questions subsidiaires)

Hello.
Pas de démonstration pour le moment. (Ça semble assez laid comme objet au premier abord) cependant une conjecture sur le pire cas.  Il me semble que si on tente de réaliser le maximum de sous graphes complets de p+1 éléments on approche la configuration qu'on désire. Malheureusement ca "tombe pas pile" en fonction de n et p (donc un peu de combinatoire derrière) mais voici un petit exemple pour des valeurs sympa N=12 et p=3.
On réalise donc 3 sous graphes complets de 4 éléments (ou chacun donc assure son quota de 3 connaissances), dans ce réseau ainsi formé on ne peut choisir qu'une personne par sous graphe pour constituer notre groupe d'inconnus, soit 3 personnes au max.

Donc pour ces rares cas ou N est multiple de p+1 je pense que le cardinal du groupe max d'inconnus dans le pire cas est (N/p+1) (En tant qu'égalité c'est une conjecture mais en tant que majorant c'est directement utilisable puis qu'on sait le construire)

Même si l'aspect combinatoire casse les possibilités de belles symétries ca serait tout de même étonnant qu'en ajoutant des gens on fasse diminuer notre groupe min. On peut également être tenté d'admettre qu'on puisse atteindre le même pire cas ou mieux avec "exactement p" qu'avec "au plus p".

Si on se laisse le droit de construire une configuration avec "au plus p" à la place de "exactement p" on peut faire le max de graphe complet de p+1 éléments puis un graphe complet plus petit avec les pas beaux qu'il reste.

Donc pour les cas ou N n'est pas multiple de p+1 je pense que le cardinal du groupe max d'inconnus dans le pire cas est soit E(N/p+1) soit E(N/p+1)+1.

Voila voila pour la partie conjecture, reste à trouver une demo qui arrive à rendre homogène cet objet relativement moche.

 #11 - 07-07-2011 17:21:11

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

toutes mes amitiés (+ questions subdidiaires)

Lorsque l'on constitue le groupe des personnes qui ne se connaissent pas, la première personne que l'on met dedans élimine forcément p personnes. La deuxième personne en élimine d'autre uniquement si elle connait d'autres personnes que la première.
Pour constituer le plus gros groupe de personnes qui ne se connaissent pas, l'idéal est de constituer des paires de groupes de p personnes où chaque personne de premier groupe de la paire connait chaque personne du 2eme groupe de la paire.



Comme nous avons n*p/2 couples de relation, nous savons qu'il y a un entier pair parmi n et p.
Montrons que cette condition est suffisante tout en construisant un gros groupe de personnes qui ne se connaissent pas.

Essayons de faire des paires de groupes de p personnes n = 2p*q+r,  0<= r <2p
Si r = 0.
Pour chaque paire de groupe de p personnes nous établissons les relations de manière optimale comme dit plus haut et nous pouvons prendre 1 groupe de chaque paire pour le groupe final. Soit le maximum possible : n/2.
Si 0< r < p.
Nous faisons q-1 paires de groupe de p personnes de manière optimale. Il nous reste 2 groupes de p personnes (P1, P2) et un groupe de r personnes (R1).
Chaque personne de R1 fait connaissance avec chaque personne de P1.
Toutes les personnes de R1 connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P1 connaissent r personnes et ne se connaissent pas entre elles.
Chaque personne de P1 fait connaissance avec p-r personnes de P2 de la manière suivante :
La première personne de P1 fait connaissance avec la première personne de P2 et les p-r-1 suivantes.
La deuxième personne de P1 fait connaissance avec la 2eme personne de P2 et les p-r-1 suivantes.
La dernière personne de P1 fait connaissance avec la dernière personne de P2 et les p-r-1 premières.
Toutes les personnes de P1 connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P2 connaissent p-r personnes.
Il nous reste a ajouter r relations aux p personnes de P2. On le fait récursivement car si p est impair, alors r est pair.
De plus on peut rajouter toutes les personnes de P1 dans l'ensemble final dont la taille sera q * p soit strictement entre n/3 (si q ->0) et n/2 (si q grand)
Si r = p
p est forcément pair.
Nous faisons q-1 paires de groupes de p personnes de manière optimale. Il nous reste 3 groupes de p personnes (P1, P2, P3).
On présente la première moitié de P1 a chaque personne de P2 et la deuxième moitié de P1 a chaque personne de P3.
Toutes les personnes de P1 connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P2 et P3 connaissent p/2 personnes et ne se connaissent pas entre elles.
Il reste a attribuer P/2 relations a un groupe de 2p personnes qui se résout récursivement de manière optimale.
On constitue encore un groupe de n/2
Sinon p < r < 2p
Nous faisons q paires de groupes de p personnes de manière optimale. Il nous reste 1 groupe de p personnes P1 et un groupe de r-p personnes R1.
Chaque personne de R1 fait connaissance avec chaque personne de P1.
Toutes les personnes de R1  connaissent p personnes et ne se connaissent pas entre elles.
Toutes les personnes de P1 connaissent r-p personnes et ne se connaissent pas entre elles.
Il reste a attribuer 2p-r relations a un groupe de p personnes qui se résout récursivement car si p est impair, alors r est pair et 2p-r aussi.
Au final nous constituons un groupe de (q*p + r-p) personnes

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)
Pour me montrer il faut bien me connaitre qui suis je (22) — Pour me montrer il faut bien me connaitre (21) — Mes amities (13) — Toutes mes amities (7) — Questions subsidiaires (6) — Exemples de questions subsidiaires (3) — Exemple de questions subsidiaires (3) — Exemple de question subsidiaire (3) — Pour me montrer il faut bien me connaitre qui suis je devinette (3) — Reponses enigmes et questions subsidiaires (3) — Que veut dire mes amities (3) — (2) — Enigme 2 nouveaux voisins table ronde (2) — Mes amitiees (2) — Pour me montrer il faut bien me connaitre enigme (2) — Question subsidiaire exemple (2) — 2em questions subsidiaires (2) — Que signifie mes amitiees (2) — (2) — Reponse 2eme question subsidiaire (2) — Comment ecrire mes amities (2) — Question subsidiaire trucmuche2013 numero3 (2) — Pour me montrer il faut bien me connaitre devinette jeux (1) — Une assemblee de n personnes + table (1) — (1) — Exemple de questions subsidiaire (1) — Comment ecrire tout mes amities (1) — Une personne connait combien de personnes (1) — Reponse a la 2eme question subsidiaire 2011 (1) — Reponse question subsidiaires 2011 (1) — Chaque personne connait au moins 7 autres personnes (1) — Question subsidiaire (1) — Exemple de questions conne (1) — Connais deux personnes de chaque (1) — Enigme que personne connait (1) — Que signifie mes amities (1) — Que veut dire mes amities (1) — Exemples de questions subsidiaire mathematique (1) — Devinette mon premier est (1) — Toutes mes amities ?rt (1) — Reponse a toutes mes amities (1) — Comment ecrire subsidiaire (1) — Comment ecrire toutes mes amitiees (1) — Questions subsidiaire (1) — Comment ecrire toutes mes amities (1) — Reponse des questionssubsidiaires 2011 (1) — Que veut dire une question subsidiaire (1) — Que veut dire question subsidiaire (1) — Question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3 (1) — Devinette avec reponse pour mr montrer il faut bien me connaitre (1) — Question subsidiaires n3 (1) — Enigme on peut me fabriquer mais je suis plus bo au naturel . plus de la moitie de la population en a. qui suis je ??? (1) — Question subsidiaire n 1 (1) — (1) — (1) — Tout mes amitie (1) — Reponses questions subsidiaire 2011 (1) — Question subsidiaire 3 et plus (1) — Comment ecrire mes amitiees (1) — Devinette pour me montrer il faut bien me connaitre (1) — Sur combien de personnes on se connait (1) — On peut dire mes amities (1) — Pour memontrer il faut bien me connaitre (1) — Indice question subsidiaire numero 3 (1) — (1) — Question on me connait (1) — Question subsidiaire n3 (1) — Mes amitiers (1) — Qustions subsidiaires 3 (1) — Enigme pour me montrer il faut bien me connaitrequi suis-je (1) — Enigme amitie (1) — Montrons que m<=1/2 (n-p) (n-p+1) theorie de graphe (1) — Questions subsidiaires 1 2 et 3 pour 2011 (1) — Exemple d une question de depart et ces questions subsidiaires (1) — Amities-questions (1) — Que veut dire une question subsidiaire (1) — Que veut dire toutes mes amities (1) — Enigme 3 subgidiaire (1) — Pour me montrer il faut bien me connaitre que suis-je (1) — Enigme combien elle connait de personnes (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