Répondre

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

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

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

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.

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

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

Salut

et Bingo !

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.

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

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

Re,

on y est presque ...

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

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 ;-)

@+

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 ?

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.

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

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums