Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 25-03-2019 16:23:47

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 897
Lieu: Seahaven island

les commères de bafouille et kacasse

Hello,

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.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 25-03-2019 20:24:56

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 692

Les commères de Bafouille et Jacassse

Bafouille !
http://www.prise2tete.fr/upload/godisdead-graphe1.png

 #3 - 25-03-2019 20:51:17

TOUFAU
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 44

Les commères de Bafouille et Jacase

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 : 822

Les commères de Bafoouille 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 : 897
Lieu: Seahaven island

Les cmmères de Bafouille et Jacasse

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
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 44

Les commères de Bafouillle 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 : 822

Les commères de Bafouille ett 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

 #8 - 28-03-2019 10:20:17

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 897
Lieu: Seahaven island

Les commères de Bafouille et Jacassse

@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 : 822

Les commères de Bafouill et Jacasse

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 : 897
Lieu: Seahaven island

Les commères de Bafoouille 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. smile 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 : 822

les commères de bafouolle 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

 #12 - 29-03-2019 14:24:45

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2927
Lieu: Luxembourg

Les commères de Bafouill eet Jacasse

Pour Bafouille, un graphe de Petersen devrait pouvoir faire l'affaire. Les trois représentations ci-dessous devraient être topologiquement équivalentes:
http://www.prise2tete.fr/upload/Franky1103-Petersen1.png
http://www.prise2tete.fr/upload/Franky1103-Petersen2.png
http://www.prise2tete.fr/upload/Franky1103-Petersen3.png
Pour Jacasse par contre, je suis à la rue et la possible dissymétrie me perturbe aussi.
Affaire à suivre ...

Edit:
En y réfléchissant, il semble normal que le graphe pour Jacasse soit dissymétrique, car sinon il serait filaire. Avec 12 sommets et 12 x 4 / 2 = 24 arêtes, le graphe de Chvatal semble fonctionner, dont voici trois représentations équivalentes (il reste cependant à rajouter les flèches).
http://www.prise2tete.fr/upload/Franky1103-Chvatal1.png
http://www.prise2tete.fr/upload/Franky1103-Chvatal2.png
http://www.prise2tete.fr/upload/Franky1103-Chvatal3.png

 #13 - 01-04-2019 20:07:45

TOUFAU
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 44

Les commères de Bafouille et JJacasse

bon d'accord vos graphes sont plus jolis que les miens smile

 #14 - 01-04-2019 22:41:10

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 897
Lieu: Seahaven island

Les commères de afouille et Jacasse

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!

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete