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 les 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 : 3066
Lieu: Luxembourg

Toutes mes amitiés (+ questiosn 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 : 901
Lieu: Seahaven island

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

toutes mes alitiés (+ questions subsidiaires)

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 : 1106
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 amitiés (+ questioons 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 (+ questions 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

Toutse mes amitiés (+ questions subsidiaires)

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

Toutes mes amtiés (+ questions subsidiaires)

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 : 901
Lieu: Seahaven island

Toutes es 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 mzs amitiés (+ questions subsidiaires)

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 : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

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 question subsidiaire (3) — Exemple de questions subsidiaires (3) — Que veut dire mes amities (3) — Reponses enigmes et questions subsidiaires (3) — Pour me montrer il faut bien me connaitre qui suis je devinette (3) — (2) — Mes amitiees (2) — Question subsidiaire exemple (2) — Que signifie mes amitiees (2) — Pour me montrer il faut bien me connaitre enigme (2) — Enigme 2 nouveaux voisins table ronde (2) — (2) — Reponse 2eme question subsidiaire (2) — Question subsidiaire trucmuche2013 numero3 (2) — Comment ecrire mes amities (2) — 2em questions subsidiaires (2) — (1) — Pour me montrer il faut bien me connaitre devinette jeux (1) — Exemple de questions subsidiaire (1) — Que signifie mes amities (1) — Une assemblee de n personnes + table (1) — Comment ecrire tout mes amities (1) — Connais deux personnes de chaque (1) — Question subsidiaire (1) — Reponse question subsidiaires 2011 (1) — Exemple de questions conne (1) — Enigme que personne connait (1) — Reponse a la 2eme question subsidiaire 2011 (1) — Que veut dire mes amities (1) — Une personne connait combien de personnes (1) — Comment ecrire subsidiaire (1) — Toutes mes amities ?rt (1) — Exemples de questions subsidiaire mathematique (1) — Chaque personne connait au moins 7 autres personnes (1) — Comment ecrire toutes mes amitiees (1) — Enigme pour trouver le mot amitie (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) — Devinette mon premier est (1) — Questions subsidiaire (1) — Que veut dire question subsidiaire (1) — Reponse des questionssubsidiaires 2011 (1) — Question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3question subsidiaire numero 3 (1) — Question subsidiaires n3 (1) — Comment ecrire toutes mes amities (1) — Devinette avec reponse pour mr montrer il faut bien me connaitre (1) — Que veut dire une question subsidiaire (1) — Pour me montrer il faut bien me connaitre que suis-je (1) — (1) — (1) — Tout mes amitie (1) — Reponses questions subsidiaire 2011 (1) — Question subsidiaire n3 (1) — Comment ecrire mes amitiees (1) — Question subsidiaire 3 et plus (1) — Indice question subsidiaire numero 3 (1) — On peut dire mes amities (1) — Pour memontrer il faut bien me connaitre (1) — Question on me connait (1) — Sur combien de personnes on se connait (1) — (1) — Devinette pour me montrer il faut bien me connaitre (1) — Enigme 3 subgidiaire (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) — Mes amitiers (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) — Question subsidiaire n 1 (1) — Question subsidiaire numero 3 (1) — Enigme combien elle connait de personnes (1) — Reponse a toutes mes amities (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