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
[+]

Écrire une réponse

Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide !
Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci.
Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Options
Sécurité

Répondez à la devinette suivante : 

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

Retour

Résumé de la discussion

MthS-MlndN
04-07-2011 12:19:31

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...

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