Potins et commères

[Patastronch]

Euh ... je comprends pas trop ta démo.

Et si selon ton raisonnement, n est le nombre minimal de commères tel que 2n-5 appels suffisent alors (n-1) est le nombre minimal de commères tel que 2(n-1)-5 appels suffisent non ?
Et qu'est ce qui m'empêche de faire ton raisonnement avec 2n-4 au lieu de 2n-5 ?
Enfin bon tout ca pour dire que j'ai pas compris grand chose, si tu pouvais préciser ou si quelqu'un qui la comprends pouvais ré-expliquer c'est pas de refus :)

Sinon pour répondre à ta question quand même, non la démo que je possède ne ressemble pas du tout à ca.

[Imod]

Pourquoi 2n-4 est-il le minimum ?

Pour n=4 ou 5 on le vérifie à la main ( je vous épargne les arbres ) .

Supposons maintenant qu'un groupe de commères puisse se renseigner en moins de 2(n+1)-4=2n-2 appels . Au moins l'une des commères a communiqué avec plus de deux de ses complices sinon alors impossible . Supposons maintenant que cette commère soit 1 et qu'elle ait téléphoné successivement à 2 ; 3 ; 4 ; ... . En retirant 1 du groupe de médisantes , en supprimant les coups de fil 1i ( i=2;3;4;...) et en ajoutant 3i (i=4;...) on obtient une bande de mégères trop performante pour l'hypothèse de récurrence .

Imod

[Patastronch]

Au moins l'une des commères a communiqué avec plus de deux de ses complices

Jusque là d'accord.

En retirant 1 du groupe de médisantes , en supprimant les coups de fil 1i ( i=2;3;4;...) et en ajoutant 3i (i=4;...) on obtient une bande de mégères trop performante pour l'hypothèse de récurrence .

Je dois commencer a me rouiller ce petit bout m'échappe.

[Imod]

Je dois commencer a me rouiller ce petit bout m'échappe.

Tiens , moi aussi ( ce qui est bien plus grave :marteau: ) . Mais j'ai une autre idée ........

Imod

[scelerat]

Prenons la commere C0 qui donne le premier coup de fil, et considerons ensuite les n-1 autres avec n-1 potins dont 1 double. Il leur faut 2n-6 coups de fil pour echanger tous leurs potins, puis 1 pour informer la commere ecartee. Peuvent-elles inclure la commere C0 dans le circuit avant ?
C0 recevrait un coup de fil et en redonnerait un qui ne contiendrait pas plus de potins. C0 peut donc etre "court-circuitee"(*) dans tout couple de coups de fils ou elle est impliquee apres le premier, puisqu'elle n'a plus d'information a ajouter.
Il n'est donc necessaire pour elle qu'un coup de fil supplementaire pour apprendre la totalite des potins
Donc si on avait une solution a moins de 2n-4 pour n, en enlevant les deux coups de fil initial et final de C0 et en court-circuitant, on en aurait une a moins de 2n-6 pour les n-1 commeres restantes, ce qui est impossible.

(*) court-circuit = remplacement du couple {C1,C0}, {C2,C0} par {C1, C2}, {C1, C2} aux memes moments.

[Patastronch]

on en aurait une a moins de 2n-6 pour les n-1 commeres restantes, ce qui est impossible.

Je saisi pas l'affirmation de ta conclusion, c 'est justement ce qu'il faut prouver non ? Que c'est impossible pour n-1 commères de tout echanger en moins de 2n-6 appels.