Potins et commères

Olympiades mathématiques, énigmes et défis
Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

Potins et commères

par Patastronch » 12 Aoû 2008, 19:24

Chacune de ces () commères connaît un potin qu'elle voudrait bien faire partager à ses complices.
Mais voilà, les commères sont dispersées ce jour-là aux coins de la ville. Heuresement, elles possèdent toutes une téléphone portable. Sachant qu'aucune n'a d'abonnement permettant la conversation à 3 (ou plus) et qu'aucune ne possède le signal d'appel, quel est le nombre d'appel minimal qui sera passé au total par ces commères pour qu'elles possèdes chacune les potins ?

N.B : Bipper quelqu'un est considéré comme un appel.

Problème tiré du journal "Le Monde" daté du mardi 14 mars 2000 (problème n°163)



Flodelarab
Membre Légendaire
Messages: 6574
Enregistré le: 29 Juil 2006, 14:04

par Flodelarab » 12 Aoû 2008, 20:17

La commère est bavarde. Si elle connait 4 secrets, elle délivre 4 secrets à son interlocutrice ?

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

par Patastronch » 12 Aoû 2008, 20:19

Oui, il suffit d'un unique coup de fil pour transmettre autant de potin qu'on veut. Et est il nécessaire de préciser qu'un appel est symétrique (que les 2 interlocuteurs peuvent parler) ? donc en un unique coup de fil, 2 commères peuvent échanger tous leurs potins mutuellement.

scelerat
Membre Relatif
Messages: 397
Enregistré le: 03 Aoû 2005, 13:37

par scelerat » 13 Aoû 2008, 10:03

Supposons que l'on divise les commeres en deux groupes aussi egaux que possible, on peut avoir une solution qui verifie (les divisions sont entieres),, . Pour cela, il suffit que chaque commere du plus grand groupe en appelle une du plus petit en s'arrangeant pour que toutes soient appelees, une fois que le probleme a ete resolu au sein de chaque groupe. Reste a expliciter et a montrer que c'e serait optimal...

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

par Patastronch » 13 Aoû 2008, 10:28

On peut faire mieux :)
Pour n=4 tu es optimal, a partir de n=5 non.

Flodelarab
Membre Légendaire
Messages: 6574
Enregistré le: 29 Juil 2006, 14:04

par Flodelarab » 13 Aoû 2008, 10:50

D'après Scelerat, T4=4
Pour n=4 tu es optimal, a partir de n=5 non.
Mince! Ça me souffle d'apprendre que le nombre de coups de fils minimum à 4 commères est 4 ! Je trouvais toujours 5.

Pour chercher, je prends 2 cobayes: n=4 et n=8


Avant d'optimiser, Je cherche à plafonner. Il y a 2 phases: apprentissage et restitution.
Il y a toujours une commère qui sait tout. Elle appelle ses n-1 amies pour savoir et encore n-2 amies pour répéter. Il faut donc au maximum 2n-3 coups de fil. Tout système dépassant ce nombre serait ridicule.

Existe t il une solution meilleure ?
pour n=8, en découpant en 2 plusieurs fois, la récolte peut se faire en 7 coups de fils, et la redistribution demande forcément 6 étapes (car seules 2 commères savent tout). Soit 13 communications, ce qui est inférieur à 2*8-3=15. Donc, OUI, il existe de meilleures méthodes que celle naïve.


Je continue de chercher.

Flodelarab
Membre Légendaire
Messages: 6574
Enregistré le: 29 Juil 2006, 14:04

par Flodelarab » 13 Aoû 2008, 10:54

D'après Scelerat, T4=4
Pour n=4 tu es optimal, a partir de n=5 non.
Mince! Ça me souffle d'apprendre que le nombre de coups de fils minimum à 4 commères est 4 ! Je trouvais toujours 5.



Avant d'optimiser, Je cherche à plafonner. Il y a 2 phases: apprentissage et restitution.
Il y a toujours une commère qui sait tout. Elle appelle ses n-1 amies pour savoir et encore n-2 amies pour répéter. Il faut donc au maximum 2n-3 coups de fil. Tout système dépassant ce nombre serait ridicule.


Je continue de chercher.
Pour chercher, je prends 2 cobayes: n=4 et n=8

Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 11:00

par Imod » 13 Aoû 2008, 11:17

J'arrive à 2n-4 appels ! Peut-on faire mieux ?

Imod

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

par Patastronch » 13 Aoû 2008, 11:45

Imod a écrit:J'arrive à 2n-4 appels ! Peut-on faire mieux ?

Imod

Non en effet on ne peut pas faire mieux :) Reste plus qu'à le prouver ! Décidément Imod, ta rapidité m'étonnera toujours :s

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 10:21

par nodgim » 13 Aoû 2008, 17:51

Bonsoir.
J'aurais dit plus modestement 2n-3 (pour les nombres impairs) :hein:

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 15:25

par leon1789 » 13 Aoû 2008, 18:27

nodgim a écrit:Bonsoir.
J'aurais dit plus modestement 2n-3 (pour les nombres impairs) :hein:

on peut effectivement prouver (via une récurrence avec quelconque) que 2n-3 appels suffisent pour tout partager.

Maintenant, l'énoncé est avec : avec cette hypothèse, on peut optimiser un appel et arriver ainsi à 2n-4 (cf. Imod)

Prouver que c'est le minimum ... ?

charlol
Membre Naturel
Messages: 66
Enregistré le: 29 Juin 2008, 11:33

par charlol » 13 Aoû 2008, 22:08

oui on a 2n-4 : tu prend la méthode de Flodelarab sur n-1 commère(s) et tu fais partager ac celle que ta laissé de coté (+1 appel) , ce qui fait : 2(n-1)-3+1=2n-4
Je suis impatient de voir une démonstration pour montrer que c'est optimal ...
J'ai du mal a en trouver une , a vrai dire je ne suis même pas convaincu que ce soit le mieu qu'on puisse faire :hum: :hum: :hum:
(mais si Patastronch le dit ...)
Charlol

Flodelarab
Membre Légendaire
Messages: 6574
Enregistré le: 29 Juil 2006, 14:04

par Flodelarab » 13 Aoû 2008, 22:24

Non Charlol. C'est faux. Le secret de celle que tu as laissée de côté ne sera connu de personne à part les 2 dernières personnes à téléphoner.



Sinon, je trouve le problème très intéressant.
J'ai commencé par la méthode naïve de l'échange centralisé. Puis j'ai je suis tombé dans l'excès inverse: partager le calcul au maximum sans rien centraliser.

Et bien si cette méthode est optimale en temps pour les puissances de 2 (plus d'appels simultanés), elle ne l'est pas quand au nombre d'appels !!!
Ainsi, pour 16 commères, si elles n'échangent qu'avec des commères n'ayant aucun secrets en communs, il leur faudra 4*8=32 coups de fil. :--:


Je cherche encore.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

par Patastronch » 13 Aoû 2008, 23:10

Oui, il faut déjà déterminer la stratégie avant toute chose :) Une fois qu'on a trouvé la stratégie, il est très facile de démontrer par récurrence que pour tout elle fonctionne a coup sure.

Sinon je vous confirme que 2n-4 est bien l'optimal pour tout . Pourquoi j'en suis sur ? parceque j'ai une démo de minimalité sous les yeux (qui n'est pas de moi au passage) et je ne doute pas que, parmi vous, bientot quelqu'un la trouvera !

Bon courage !

charlol
Membre Naturel
Messages: 66
Enregistré le: 29 Juin 2008, 11:33

par charlol » 14 Aoû 2008, 00:25

oupf , dsl , j'ai dis nimporte quoi
charlol

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

par Patastronch » 14 Aoû 2008, 00:41

Innutile de t'excuser, ca arrive à tout le monde :)

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

par Patastronch » 14 Aoû 2008, 11:29

Un conseil pour trouver la stratégie, raisonnez pour ca suffit. étant le cas limite la généralisation est moins transparente.

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 10:21

par nodgim » 14 Aoû 2008, 16:38

OK pour moi pour 2n-4 :id:

La stratégie est de faire échanger les infos toutes distinctes, afin d'éviter les redondances.
Exemple pour n=7
12;12;34;34;56;56;7 puis 1234;12;1234;34;567;56;567 puis
1234567;12;1234567;34;1234567;56;1234567; et encore 3 coups de fils pour finir.
Généralité: n-1 échanges pour avoir 2 commères au courant de tous les potins. Un échange supplémentaire pour que 2 autres commères soient dans le même cas. Enfin, n-4 coups de fils pour les n-4 commères restantes.
n-1+1+n-4=2n-4

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 22 Aoû 2005, 23:53

par Patastronch » 14 Aoû 2008, 18:13

Oui, ta stratégie varie légèrement de celle que j'avais en tête mais c'est la même idée. La clef est bien entendu la complémentarité des infos.

Donc une stratégie possible pour clarifier :
1@2 ; 1@3 ; 1@4 ; ... ; 1@(n-2) soit n-3 appels
(n-1)@n ; (n-1)@1 soit 2 appels
n@(n-2) ; n@(n-3) ; n@(n-4) ; ... ; n@2 soit n-3 appels
total => 2n-4 appels

Reste à démontrer que ça marche pour tout n (sans réelle difficulté) et reste à prouver que c'est le minimum :)

magnolia86
Membre Relatif
Messages: 155
Enregistré le: 14 Aoû 2008, 17:59

par magnolia86 » 14 Aoû 2008, 19:01

2n-4 est le minimum : preuve par l'absurde.

Soit n le nombre minimal pour lequel 2n-5 appels suffisent.
Quitte à renuméroter les commères, on peut supposer que le premier coup de fil est entre C_n et C_{n-1}.

Comme C_n ne connait pas tous les secrets (), il lui faudra un second coup de fil avec, disons, C_i avec .

Maintenant il reste 2n-5-2=2(n-1)-5 ( > 0 car ) appels possibles pour les n-1.
Mais par minimalité de n, les n-1 premières commères ne peuvent pas partager leur secret...

Ca doit ressembler à ça, non ?

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 9 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite