![](/img/vague-bas-gauche.png) |
#1 - 25-03-2019 16:23:47
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
les commèees de bafouille et jacasse
Hello,
![http://www.prise2tete.fr/upload/Clydevil-net.png](http://www.prise2tete.fr/upload/Clydevil-net.png)
Une petite histoire de commères, de ragots, et de coup de fil.
Dans le petit village de Bafouille: - il y a 10 commères. - chacune à exactement 3 amies (c'est symétrique: si a amie de b alors b amie de a) - lorsqu'une d'entre elle apprend un ragot, elle le communique à toutes ses amies. Comment peuvent elles organiser leur réseau, pour que quelque soit celle qui apprenne un ragot, n'importe quel autre soit au maximum à 2 coups de fils de l'apprendre?
Dans le petit village de Jacasse: - il y a 12 commères - chacune a le numéros d'exactement 2 autres à qui elle aime communiquer des ragots (pas forcement symétrique cette fois) Comment peuvent elles organiser leur réseau, pour que quelque soit celle qui apprenne un ragot, n'importe quel autre soit au maximum à 3 coups de fils de l'apprendre?
Bonne chance!
NB: et je suis curieux d'avoir une estimation de la difficulté ou du temps passé sur chaque variation de ce problème.
#2 - 25-03-2019 20:24:56
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
Les commères de Bafouille et Jaasse
Bafouille !
![http://www.prise2tete.fr/upload/godisdead-graphe1.png](http://www.prise2tete.fr/upload/godisdead-graphe1.png)
#3 - 25-03-2019 20:51:17
- TOUFAU
- Professionnel de Prise2Tete
- Enigmes résolues : 0
- Messages : 105
Les commères de Bafouille et Jaasse
Bonjour Clydevil.
Alors d’abord j’interprète le pb (peut-être à tort) : - « lorsqu'une d'entre elle apprend un ragot, elle le communique à toutes ses amies » = 1 coup de fil. C’est plus un groupe WhatsApp, quoi. Les autres options que j’avais envisagées n’ont pas de sens ("1 amie prévenue = 1 coup de fil"… ça ne marche pas de tout, je fais pas un dessin. Ou « communiquer aux amies du réseau = 0 coup de fil ». Marche pas non plus, dans ce cas toutes sont instantanément au courant car il n’y a pas de ‘groupe fermé’ de 4 copines au sein d’un groupe de 10 ou toutes ont 3 amies. Moins vrai dans un groupe de 8…) - « Comment peuvent-elles organiser leur réseau » = comment elles choisissent leur groupe d’amies. Le ragot prévaut sur l’amitié en quelque sorte. Je me fous d’avec qui je suis copine, l’important c’est d’être prévenu vite sur WhatsApp. Ça ne ressemble pas du tout aux femmes que je connais… (je plaisante bien sûr) Dans ce cas, exemple de solution au problème de Bafouille (en sélectionnant une ligne quelconque, et les 3 qui ont un X dans la ligne sélectionné, on voit vite que ça marche).
1 2 3 4 5 6 7 8 9 10 1 X X X 2 X X X 3 X X X 4 X X X 5 X X X 6 X X X 7 X X X 8 X X X 9 X X X 10 X X X
Quant au temps passé (à ne chercher qu'un exemple donc), je dirais à la louche dans les 19’ à interpréter le pb, dans les 31’ à essayer de le résoudre, 5’28 à poster. Mais c’est approximatif bien sûr.
Résultat plus de temps pour réfléchir à Jacasse, qui à l'air aussi d'un bel îlot de commères. La symétrie en moins.
#4 - 26-03-2019 09:12:15
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Les commères d eBafouille et Jacasse
Salut Clydevil,
pour le premier problème, j'ai trouvé en quelques minutes un graphe qui convenait, que j'ai identifié après moteur de recherche comme le graphe de Petersen (ce qui m'évite d'avoir à le dessiner).
Pour le second, j'ai cherché une petite heure, j'ai notamment essayé avec un cuboctaèdre, mais je pense pouvoir prouver que c'est impossible avec ce graphe-ci. Quand j'aurai un moment, j'essaierai avec d'autres graphes.
#5 - 27-03-2019 11:17:16
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
les commères de bafouille et jacadse
Intéressant, 3 réponses pour la version Bafouille dans un ordre de temps de 30 minutes passées disons. Le cas Jacasse semble nettement plus dur.
#6 - 27-03-2019 19:21:47
- TOUFAU
- Professionnel de Prise2Tete
- Enigmes résolues : 0
- Messages : 105
Les comèmres de Bafouille et Jacasse
Bonjour Clydevil.
J'ai trouvé un moment pour Jacasser. En partant du principe que je ne vois pas de raisonnement logique sur les graphes qui m'amène une solution par l'intelligence, je cherche une solution par la force (quand on n'a pas de tête...) Du coup, un xls avec quelques formules qui me disent si la solution marche ou pas. -> un peu plus d'1 heure. Ensuite recherche (en partant du principe '0 redondance sur le coup de fil 2', sinon il faut 0 redondance sur le coup de fil 3...) Je trouve ça qui marche (les colonnes informent les lignes) 1 2 3 4 5 6 7 8 9 10 11 12 1 X X 2 X X 3 X X 4 X X 5 X X 6 X X 7 X X 8 X X 9 X X 10 X X 11 X X 12 X X
Brutal... mais 30' max à rechercher. Du coup 1h30 (et un xls que je vais peut être commercialiser) Toufau
#7 - 27-03-2019 19:23:34
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Les commères de Bafuoille et Jacasse
J'y ai passé encore 1h30. Cette fois-ci, mon idée, c'était de recourir à un programme pour tester tous les graphes potentiels. J'ai donc commencé à démontrer des petits résultats pour éliminer certains graphes, afin que le temps de calcul devienne raisonnable, quand j'ai essayé de démontrer qu'il n'y avait pas de paire de commères telle que chacune a le numéro de l'autre.
Évidemment, cette conjecture était fausse. Et si je ne me suis pas trompé dans mon étude manuelle, il n'existe qu'un seul graphe de ce type qui convienne (tel qu'il existe au moins une paire de commères telle que chacune a le numéro de l'autre). Le voici.
![http://www.prise2tete.fr/upload/Ebichu-commere.png](http://www.prise2tete.fr/upload/Ebichu-commere.png)
#8 - 28-03-2019 10:20:17
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Les commères de Bafouille et Jcasse
@TOUFAU: Bravo! @ebichu: Bravo aussi et je suis curieux de savoir comment toi ou ton programme vous rendez compte des symétries du graphe en question (ce qui fait que son dessin est si beau).
#9 - 28-03-2019 19:38:23
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
les commères de bafouille et hacasse
Je ne comprends pas la question ? Je n'ai pas fait de programme : c'était prévu, mais je me suis rendu compte de l'existence de ce graphe avant de commencer à programme.
Je n'y peux rien s'il est symétrique, c'est le seul qui ait deux commères en relation, et il se trouve qu'il est comme ça. Sinon je l'ai tracé avec Inkscape, c'est moi qui ai placé les sommets où ils se trouvent.
#10 - 29-03-2019 08:52:46
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Les commères de Bfouille et Jacasse
@Ebichu: Ha, j'avais compris qu'un programme t'avais permis d'au moins retirer certaines possibilités. Ok c'est plus clair. "Il se trouve qu'il est symétrique" oui, lol, mais c'est bien moins trivial que tu penses de représenter symétriquement (se rendre compte de la symétrie) un graphe symétrique. Donc vu ta réponse j'en déduis que tu l'as "démêlé" à la main en identifiant les nœuds qui jouent le même rôle. bravo en tout cas. (Ce graphe porte un nœud et a une propriété particulière, je la donnerais après l’énigme)
#11 - 29-03-2019 10:02:55
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Les commères de Bafouile et Jacasse
En effet, je l'ai démêlé à la main : j'ai le réflexe, dès que je tombe sur un graphe, d'essayer de le représenter clairement. Celui-ci avait 2 triangles et 3 "diangles", et en voyant ces objets comme 5 composantes distinctes, le graphe se dessine simplement.
D'ailleurs, j'ai sacrifié une des symétries sur l'autel de la planarité, car les 3 sommets les plus à l'extérieur ont le même rôle que les 3 sommets centraux sur mon dessin.
Et puis je ne connais pas le nom de ce graphe donc j'attends la fin avec intérêt ![smile](img/smilies/smile.png)
#12 - 29-03-2019 14:24:45
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
Les commères de Bafouill et Jacasse
#13 - 01-04-2019 20:07:45
- TOUFAU
- Professionnel de Prise2Tete
- Enigmes résolues : 0
- Messages : 105
Les commères de Bafouille et Jacsase
bon d'accord vos graphes sont plus jolis que les miens ![smile](img/smilies/smile.png)
#14 - 01-04-2019 22:41:10
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
les commères de bafouille et javasse
Bravo à tous les participants!
Quelques précisions: -Le graphe pour le cas non orienté se nomme graphe de Petersen. https://en.wikipedia.org/wiki/Petersen_graph -Le graphe pour le cas orienté fait parti d'une famille nommé digraphe de Kautz https://en.wikipedia.org/wiki/Kautz_graph Vous pouvez voir sur cette page le cas ABC qui correspond à l’énigme. Cette seconde question donne donc quelque chose qui se généralise (qui est efficace mais je ne sais pas si c'est démontre minimal pour les autres tailles du problème).
Plus généralement toutes ses questions se rapprochent des problématiques degree-diametre dans les graphes.
On peut trouver des informations ici: http://combinatoricswiki.org/wiki/The_D … ral_Graphs http://combinatoricswiki.org/wiki/The_D … l_Digraphs
Ce qui me passionne dans ces structures n'a qu'un rapport éloigné avec la communication, je reflechissais à comment un organisme doit s'organiser pour être capable de se reconstruire de la manière la plus robuste. Ça se rapproche des problématiques de programmes avec codes correcteurs mais dans un cas ultraparallelisé (ou chaque cellule ou agent agit parallelement avec les autres pour assurer l'intégrité du tout)
Voila voila!
|
![](/img/vague-haut-droite.png) |