Radio moquette ...

freddy · 12-07-2011 14:50:15

Hello,

trouvé sur le net. Attention, c'est velu !

Enoncé

Par diverses rumeurs, n concierges d'immeubles de très grand standing ont eu connaissance du dernier scandale qui secoue la ville de NY.

Chacune dispose d’informations très partielles qui ne se recoupent pas nécessairement entre elles.

Toutes réunies, elles parviendraient à reconstituer l’histoire complète de ce scandale.

Au cours de conversations téléphoniques exclusivement bilatérales, elles échangent toutes les informations en leur possession et à l’issue d’un nombre minimal de cent appels téléphoniques, elles parviennent à tout savoir du scandale.

Combien vaut n ?

Question bis

Ces mêmes concierges décident de mieux se connaître et de se rendre visite en tête-à-tête.

N’importe quelle concierge peut répondre à plusieurs invitations dans une même journée ; toutefois, celle qui reçoit une ou plusieurs "début d'amies" successivement dans une journée ne peut quitter son domicile le même jour.

Quel est le nombre minimum de journées qui permettraient à chaque concierge de rencontrer toutes ses autres consoeurs ?

jpp · 12-07-2011 18:42:55

Bonsoir

si un appel entre 2 concierges a et b est unique, peut-etre qu'une seule a pu récupérer toutes les infos.

a) en conversant avec un premier groupe de 10 ce qui fait [tex] \frac{11!}{2!\times{9!}}= 55 échanges[/tex]

ce serait elle qui aurait fait les 10 derniers appels avec ce groupe

b) en conversant d'un autre coté avec 9 autres concierges [tex]\frac{10!}{2!\times{8!}} 45 échanges[/tex]

ce serait encore elle qui aurait fait les 9 derniers appels avec cet autre groupe
et enfin effectué tous les recoupements

pour faire la reconstitution des evenements.

ce qui ferait à mon avis 20 concierges au total avec 100 coups de telephone.

Et en 5 jours elles ont fait connaissance de cette façon.

il doit y avoir 190 rencontres

premier jour, 10 hotes recoivent 10 invités ---> 100 échanges. et un groupe H de 10

et un groupe I de 10

deuxième jour 5 de chaque groupe reçoit 5 de leur groupe respectif ---> 2 x 25 = 50

troisième jour 3 de chaque groupe de 5 reçoit les 2 autres de ces meme groupes. ->4 x 6 = 24

quatrième jour 8 rencontres parmi les 4 groupes de 3 et 4 rencontres avec les 4 groupes de 2

8 + 4 = 12

le cinquième jour pour les 4 dernières rencontres .

Dernière modification par jpp (12-07-2011 20:24:40)

jpp · 13-07-2011 11:55:43

Bonjour.

Ou alors si toutes doivent recevoir les memes informations alors, 14 s'échangent 91 appels

ensuite 9 autres apprennent la totalité des infos

en appelant une ou l'autre des 14 premières. ce qui fait 23 concierges.

freddy · 13-07-2011 12:23:48

Salut,

20 n'est pas le nombre recherché.

Il est dit que chaque concierge détient un bout d'information et que la réunion de tous ces bouts d'information permet d'avoir la vérité. Il est dit qu'au bout d'au moins 100 coups de fil, elles sont parfaitement informées !

Il est précisé que si toutes les concierges pouvaient échanger en même temps leur information, elles sauraient la vérité.

Private joke
Ceci étant dit, la vérité, on la connait : DSK n'a rien fait et la femme en robe de chambre non plus. Tout ça c'est rien que de la mauvaise malveillance malveillante, pas plus.

La preuve ? Avec un Français, aucune femme n'a jamais eu à se plaindre, même pas celle de nerosson, c'est pour dire !

Dernière modification par freddy (14-07-2011 07:50:52)

jpp · 13-07-2011 21:51:33

Re .

on imagine que 10 concierges détiennent les éléments d'un texte dont il manque la fin.

ce morceau de texte étant fragmenté en 10

on imagine aussi que 9 autres concierges détiennent les éléments du meme texte dont il manque le

début. ce morceau de texte étant fragmenté en 9

alors pour connaitre le texte en son entier 45 appels entre les 10 + 10 appels pour connaitre

la fin donne 55 appels

de meme pour connaitre le texte en son entier 36 appels entre les neuf autres + 9 appels pour

connaitre le début . ce qui donne 36 + 9 = 45 . soit en tout 100 appels.

il n'y aurait donc 19 concierges.

longueur du texte ----------- -------- --------- -------- -------- -------- --------- ------- ------- ------- ---- ---

chaine de 10 ----------- -------- -------- -------- -------- -------- -------- -------- ------- -------

chaine de 9 ---------- -------- ------- -------- ------ ------- ------- ------ ------- ----------------

donc [tex] n = 19[/tex]

freddy · 14-07-2011 08:30:34

Re,

toujours pas. Il faut bien lire l'énoncé.

yoshi · 14-07-2011 11:08:11

Re,

Hmmm....

Au cours de conversations téléphoniques exclusivement bilatérales, elles échangent toutes les informations en leur possession et à l’issue d’un nombre minimal de cent appels téléphoniques, elles parviennent à tout savoir du scandale.

S'il y a n concierges échangeant des conversations bilatérales, cela revient au problème des poignées de main, non ?
Il y a alors n(n-1)/2 conversations...
Mais je tombe sur 105 conversations et pas 100 avec 14*15/2 et 15 concierges...
Il y a un os dans mon potage ?

@+

jpp · 14-07-2011 12:39:23

Salut a tous.

Yoshi , avec 15 concierges pour éviter 5 coups de teléphone il suffirait peut-etre que 1 concierge

détienne à elle toute seule 5 infos , et que 5 concierges détiennent chacune une de ces infos

donc le nombre de coup suffisant serait [tex] C_{15}^{2} - 5 = 100[/tex]

à plus.

nerosson · 14-07-2011 13:01:46

Salut à tous

Freedy a écrit :

Private joke
Ceci étant dit, la vérité, on la connait : DSK n'a rien fait et la femme en robe de chambre non plus. Tout ça c'est rien que de la mauvaise malveillance malveillante, pas plus.
La preuve ? Avec un Français, aucune femme n'a jamais eu à se plaindre, même pas celle de nerosson, c'est pour dire !

J'ai souvent essayé de violer ma femme, j'ai jamais pu : elle était toujours consentante ! ! !

jpp · 14-07-2011 13:46:17

Re .

si le total des infos dont disposent toutes les concierges totalise 4 fois la meme phrase partitionnée de

4 façons différentes.

la première en 6 partitions , la seconde en 7 , la troisième en 8 et la quatrième en 9.

alors [tex] C_{6}^{2} + C_{7}^{2} + C_{8}^{2} + C_{9}^{2} = 100[/tex]

on obtient donc [tex] n = 6 + 7 + 8 + 9 = 30[/tex]

et en 4 jours les présentations sont faites pour une qui s'est toujours déplacée et pour la seconde qui

n'a reçu qu'une fois.

en 5 jours pour les 28 autres.

Dernière modification par jpp (14-07-2011 14:06:53)

freddy · 14-07-2011 14:07:58

freddy a écrit :

Hello,
trouvé sur le net. Attention, c'est velu !
Enoncé
Par diverses rumeurs, n concierges d'immeubles de très grand standing ont eu connaissance du dernier scandale qui secoue la ville de NY.
Chacune dispose d’informations très partielles qui ne se recoupent pas nécessairement entre elles.
Toutes réunies, elles parviendraient à reconstituer l’histoire complète de ce scandale.
Au cours de conversations téléphoniques exclusivement bilatérales, elles échangent toutes les informations en leur possession et à l’issue d’un nombre minimal de cent appels téléphoniques, elles parviennent à tout savoir du scandale.

En clair, un contact ne suffit peut être pas ; à la fin, toutes savent de quoi il en retourne, pas une seule (c'est normal, ce sont des concierges ...).

Capisci ?

Dernière modification par freddy (14-07-2011 14:15:50)

yoshi · 14-07-2011 17:24:12

Ave,

Non, ça ne m'apporte rien de plus - tout au contraire - sinon une certitude : c'est pas pour moi !
Je ne vais pas ergoter...
Ah ! freddy, désolé ! Ton quote me rappelle un de mes profs de maths dans le supérieur qui nous envoyait sécher au tableau et quand on avait assez mariné, se plantait devant nous, désignait le tableau et nous disait :
<< Mais mon pauvre ami, vous prenez un marteau-pilon pour écraser une mouche...! Relisez donc votre énoncé ! >>
Qu'est-ce qu'on était contents...
Bon 15 concierges pour NY, ça faisait peu...
Je n'avais pas pris garde qu'on recommençait à jouer avec des peut-être, des "pas nécessairement", alors permettez que je me retire sur la pointe des pieds...
Ne vous dérangez pas, je refermerai soigneusement la porte en sortant : je retourne jouer aux billes avec les "vieux" gamins de ma rue ;-)

@+

Dernière modification par yoshi (14-07-2011 18:47:28)

jpp · 15-07-2011 07:14:39

Bonjour.

si c'est un puzzle ..

la première en appelle 9 autres = 9 coups de fil ---> elle en sait pour 10

les 9 autres se concertent 2 par 2 => 36 coups de fil --> les 10 en savent autant

9 + 36 = 45 coup de fil.

ensuite , 9 en appellent 9 autres ---> 45 + 9 = 54 coups de fil et ce sont ces 9 dernières qui

vont à leur tour se concerter => 36 coups de fil de plus et elles savent tout ---> 36 + 54 = 90

coups de fil.

les 9 dernières rappellent les 9 précédentes ---> 90 + 9 = 99 coups de fil et l'une d'elle

appelle la première. 99 + 1= 100 coups de fil et j'ai [tex] 19 concierges. [/tex]

autrement une en appelle 2 autres qui s'appellent aussitot --> 3 appels

après la chaine commence une des 3 appelle une 4ème qui appelle une 5ème qui appelle ......

..... qui appelle une 51ème qui en sait donc autant que la 50ème. => 48 + 3 = 51 appels .

la chaine repart dans l'autre sens à partir de la 50ème jusqu'à la première = 49 appels.

total 49 + 51 = 100 appels et [tex]51 concierges[/tex].

Dernière modification par jpp (15-07-2011 07:16:15)

freddy · 15-07-2011 08:07:55

Re,

on y est presque ...

jpp · 15-07-2011 09:10:09

Re

la première appelle 2 concierges qui vont s'appeler aussitot. puis elles appellent toutes les 2 une 4ème.

les 3 concierges possèdent donc 4 pièces du puzzle après 5 coups de fil.

La première n'ayant que 3 pièces en reste là.

les 3 autres se partage la tache en appelant 13 concierges --> 13 + 5 = 18 coups de fil.

les 13 se concertent pour avoir 13 + 4 = 17 pièces du puzzle.

elles donnent donc 78 coups de fil ---> 18 + 78 = 96 coups de fil.

il reste à renseigner les 4 premières. --> 96 + 4 = 100 et [tex] 17 concierges [/tex]

Le rendement est moins bon.

Dernière modification par jpp (15-07-2011 09:17:09)

jpp · 15-07-2011 17:47:22

Re.

j'ai aussi [tex] n = 42 [/tex] 1 appelle 2 qui appelle 3

2 et 3 appellent respectivement 4 et 5 qui s'appellent entre elles et ces dernières appellent 6 et 7

qui s'appellent entre elles.............. 40 et 41 qui s'appellent entre elles .

41 appelle 42 . ces 2 dernières savent tout. et appellent les 40 premières .

à plus.

jpp · 17-07-2011 10:53:48

Bonjour.

je pense informer 52 concierges en 100 coups de fil

Avec 2 chaines de 26. une chaine A et une chaine B

Au bout de 25 coups de fil par chaine , alors A₂₅ et A₂₆ d'une part

et B₂₅ et B₂₆ d'autre part sont également informées.

Donc en 2 coups de fil elles partagent leurs infos et savent tout.

Il leur reste donc à informer les 48 autres en 48 coup de fil.

freddy · 17-07-2011 11:09:54

Salut

et Bingo !

totomm · 17-07-2011 11:28:59

Bonjour,

freddy a écrit :

Chacune dispose d’informations très partielles qui ne se recoupent pas nécessairement entre elles.

si l'on suppose que chaque concierge détient au moins une bribe d'information qu'aucune autre ne détient, et si il y a 51 concierges, une des concierges peut avoir 50 conversations téléphoniques exclusivement bilatérales pour tout savoir, et à l'issue de la 50-ème conversation téléphonique exclusivement bilatérale, elles sont 2 à tout savoir.
Il suffit alors à l'une des 2 qui sait tout d'avoir 49 conversations téléphoniques exclusivement bilatérales pour que les 51 soient au courant de tout : Donc n > 51 car il a suffi de 99 conversations téléphoniques exclusivement bilatérales pour que toutes soient au courant de tout. et l'énoncé dit :

freddy a écrit :

à l'issue d’un nombre minimal de cent appels téléphoniques, elles parviennent à tout savoir du scandale. .

Par ce procédé indiqué, le nombre maximal de conversations téléphoniques exclusivement bilatérales est (2n-3)
Prenons n = 52. Par le même procédé il faudra un maximum de 101 conversations téléphoniques exclusivement bilatérales pour que toutes soient au courant de tout.
Mais 101 est-il le minimum ? Tout semble dépendre du "nécessairement" introduit dans l'énoncé….

Cordialement

jpp · 17-07-2011 18:36:08

Re.

Pour répondre à la seconde question, 6 jours sont nécessaires pour faire connaissance.

Le nombre de rendez-vous : [tex]n = C_{52}^{2} = 1326[/tex] décomposés ainsi:

1^er jour 26hotes reçoivent chacune 26 invitées----> 676

2^ème jour:
a) parmi les hotes de la veille , 13 hotes reçoivent 13 invitées --->169

b) parmi les invitées de la veille , 13 hotes reçoivent 13 invitées--->169

3^ème jour: meme schéma 4 groupes de 7 hotes reçoivent respectivement 4 groupes de 6 invitées ---> 168

4^ème jour:
a) 4 groupes de 4 hotes reçoivent respectivement 4 groupes de 3 invitées -->48

b) 4 groupes de 3 hotes reçoivent respectivement 4 groupes de 3 invitées -->36

5^ème jour:
a) 4 groupes de 2 hotes reçoivent respectivement 4 groupes de 2 invitées -->16
b) 12 groupes de 2 hotes reçoivent chacun 1 invitée -->24
6^ème jour 20 hotes reçoivent 1 invitée. ---> 20

mais je vais revoir de plus près la fin car je flaire un piège au 6^ème jour

p.s. je pense que ça doit etre cela.
à plus.

Dernière modification par jpp (17-07-2011 19:34:14)

freddy · 19-07-2011 08:23:58

Salut,

exact, 6 jours !

Pour la formule 2n-3, c'est OK sauf qu'on peut faire un poil mieux. Pour n > 3 et formons deux groupes G1 et G2 de taille m et p tels que m+p=n.

X appelle un à un tous les éléments de G1 et finit par Y ; Z fait de même et finit par T. Donc m-1 et p-1 appels. Puis X joint Z et Y joint T. Soit n appels et 4 concierges parfaitement informées. Elles doivent ensuite passer n-4 appels pour informer tout le monde, soit 2n-4.

J'avais prévenu, c''était un peu velu.

Bb

totomm · 19-07-2011 10:28:36

Bonjour,

@freddy : Merci, c'est mieux quand les choses sont claires et bien démontrées. Je pensais bien qu'il devait y avoir mieux que 2n-3 et le dialogue croisé à 4 n'est pas intuitif d'entrée.
J'espère que yoshi n'est pas déçu par la démo que n > 51...

Est-ce que "velu" est la traduction contractée de "very difficult" ? :-)

cordialement

totomm · 19-07-2011 17:22:20

reBonjour,

La solution 2n-4 m'a fait repenser au démon de Maxwell censé trier les particules rapides : il est démontré que ce démon doit "acquérir de l'information" pour trier efficacement et que cette acquisition se fait à un coût qui compense l'avantage obtenu en séparant les particules….
De même,
entre les 2 groupes G1 (X-Y)et G2 (Z-T), avant que X joigne Z et Y joigne T, il faut peut-être que X et Y
soient certains que Z a fini de contacter T (son dernier à être appelé dans G2), d'où peut-être quelque conversation téléphonique supplémentaire …?
Ce pourrait être du genre : Celle de X ou Z qui a fini d'appeler dans son groupe appelle l'autre. Alors, si c'est X qui a fini en premier, c'est Z qui rappellera X et T qui rappellera Y…

J'ai ainsi fini de couper les cheveux en 2n-4 :-)

Cordialement

Forum de mathématiques - Bibm@th.net

#1 12-07-2011 14:50:15

Radio moquette ...

#2 12-07-2011 18:42:55

Re : Radio moquette ...

#3 13-07-2011 11:55:43

Re : Radio moquette ...

#4 13-07-2011 12:23:48

Re : Radio moquette ...

#5 13-07-2011 21:51:33

Re : Radio moquette ...

#6 14-07-2011 08:30:34

Re : Radio moquette ...

#7 14-07-2011 11:08:11

Re : Radio moquette ...

#8 14-07-2011 12:39:23

Re : Radio moquette ...

#9 14-07-2011 13:01:46

Re : Radio moquette ...

#10 14-07-2011 13:46:17

Re : Radio moquette ...

#11 14-07-2011 14:07:58

Re : Radio moquette ...

#12 14-07-2011 17:24:12

Re : Radio moquette ...

#13 15-07-2011 07:14:39

Re : Radio moquette ...

#14 15-07-2011 08:07:55

Re : Radio moquette ...

#15 15-07-2011 09:10:09

Re : Radio moquette ...

#16 15-07-2011 17:47:22

Re : Radio moquette ...

#17 17-07-2011 10:53:48

Re : Radio moquette ...

#18 17-07-2011 11:09:54

Re : Radio moquette ...

#19 17-07-2011 11:28:59

Re : Radio moquette ...

#20 17-07-2011 18:36:08

Re : Radio moquette ...

#21 19-07-2011 08:23:58

Re : Radio moquette ...

#22 19-07-2011 10:28:36

Re : Radio moquette ...

#23 19-07-2011 17:22:20

Re : Radio moquette ...

Réponse rapide

Pied de page des forums