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 - 23-01-2017 12:53:49

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

Mertoptimal

Hello!

https://i.ytimg.com/vi/DOg4m2YFtk8/maxresdefault.jpg
(Ma traditionnelle image qui sert à rien mais rend le post plus vivant)

Hello!
On va construire un réseau de métro! Dans notre petite ville, il y a des stations, et deux lignes de métro. Une ligne de métro c'est simplement un cycle de stations qui peut être pris dans les 2 sens.  Par exemple si on a les arrêts  A,B,C,D et E dans notre ville, on peut décider de construire la ligne BDAE avec laquelle en un seul arrêt on peut aller par exemple de B à D ou E, ou de D à A ou B.
Donc comme je le disais, dans notre petite ville on ne dispose que de deux lignes, et par contrainte on aimerait pouvoir aller de n'importe quel arrêt à n'importe quel autre en deux arrêts maximum (2 segments de lignes ou moins, mais on a le droit de changer de ligne, une fois donc).

Avec ces contraintes, combien d’arrêts au maximum peut on desservir sur notre ville?

Bonne chance!

Solution:
Spoiler : [Afficher le message] @tout le monde: Merci à tous les participants, il y a au moins la solution de ebichu qui à tête validée par excel, et il semble y avoir des preuves que 16 et 17 ne sont pas possibles. Bravo donc à ceux ayant trouver une solution valide avec 15 villes!



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 23-01-2017 18:32:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

Mteroptimal

Vu comme c'est présenté, j'imagine donc qu'une station ne peut avoir que 4 directions possibles, 2 par ligne. On suppose qu'une ligne ne déssert une station qu'une seule fois ? Si oui, alors tu ne peux pas avoir plus de 12 stations. Car 4 directions depuis n'importe quelle station, et 3 autres possibles après la 1ère station desservie. Reste à vérifier qu'on peut réaliser un tel réseau.

 #3 - 23-01-2017 20:18:53

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

MMetroptimal

J'ai un réseau avec 7 stations. 2 boucles de 5 arrêts avec 3 stations en commun.

 #4 - 23-01-2017 20:42:34

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,633E+3

Mteroptimal

Je dirais intuitivement 11 stations, dont la solution est relativement simple.

Au-delà, j'ai de sérieux doutes.

 #5 - 23-01-2017 21:26:30

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

MMetroptimal

@nodgim: Avoir une majoration et ensuite trouver un réseau qui l’atteint est une bonne démarche. Mais je ne suis pas d'accord avec ta majoration smile

@godisdead: On peut faire mieux.

@gwen27: Il y a une majoration qui est plus grande que ta proposition et qui semble avoir beaucoup de marge, je n'ai pas la solution moi même mais je serais étonné que la marge ne soit pas suffisante pour faire mieux. A creuser.

 #6 - 23-01-2017 22:48:21

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,633E+3

Metroptiml

Si on ne peut pas repasser 2 fois par le même point pour un trajet : 11

Sinon, autant que l'on veut.

 #7 - 24-01-2017 07:46:55

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

metrpptimal

Oui, j'ai tout simplement mal compté, le max est 17 et non 12.
Reste à construire les liaisons qui vont avec. Ce n'est pas le plus facile....

 #8 - 24-01-2017 10:18:13

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 429

Mertoptimal

J'ai une majoration avec 17 sommets, pardon, "arrêts" :
* Chaque sommet est de degré 2 ou 4 suivant qu'il est situé sur une ou deux lignes, donc au plus 4.
* Prenons un sommet S. S est relié à au plus 4 sommets, et chacun de ces 4 sommets, à au plus 3 autres. Quant aux autres sommets, ils seraient à une distance de S supérieure à 2. 1+4+4*3=17, cqfd.

Sinon, voici une solution avec 13 sommets :
http://www.prise2tete.fr/upload/Ebichu-metroptimal.png

Je n'ai pas encore beaucoup cherché et je ne vois pas a priori de raison pour laquelle ce ne serait pas possible avec 17. Je continue à réfléchir.

 #9 - 24-01-2017 10:24:10

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

Metroptimla

@Ebichu: Très bien! on en est au même point. Il y a sans doute encore mieux. A creuser.

@Gwen27: On a pas forcement le max pour le moment mais au moins on a strictement mieux que ta proposition.

 #10 - 24-01-2017 11:51:58

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 429

Metrpotimal

Et voici une solution avec 15 sommets :

http://www.prise2tete.fr/upload/Ebichu-n15.png

Ça devient de plus en plus tendu, donc j'ai bon espoir, soit de trouver un graphe pour 16 ou 17, soit de montrer que ça ne peut exister.

Note pour plus tard : faire une version plus lisible de ce sac de noeuds smile

 #11 - 24-01-2017 11:59:08

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

metroptimzl

Il y a des solutions simples pour 11 et 13 stations.

Pour 11, la ligne 1 prend les stations de 1 à 11 dans l'ordre (puis retour à 1), la ligne 2 dessert, après la station n, la station n+4 modulo 11.

Pour 13, la ligne 1 prend les stations de 1 à 13 dans l'ordre (puis retour à 1), la ligne 2 dessert, après la station n, la station n+5 modulo 13.

ça se passe bien avec 11 et 13 qui sont premiers, ça permet d'avoir un pas unique pour la ligne 2. Avec ces constructions, si ça marche pour une station, ça marche forcément pour les autres.

 #12 - 25-01-2017 08:04:31

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

etroptimal

Ma ligne de métro, en forme de fleur à pétales, est constituée de n+1 stations: une station centrale O et n stations périphériques S(n). Le cheminement en boucle du métro est: O – S(1) – O – S(2) – O S(3) – O – …..– O – S(n) – O – S(1). Pour les besoins de l’énigme, je peux superposer une seconde ligne identique centrée aussi sur O. De cette manière, je peux passer de n’importe quelle station en maximum deux arrêts.
Avec ce réseau, je pourrai avoir une infinité de stations répondant à la question, mais sans doute non conforme à l’esprit de ton énigme. Faut-il rajouter dans l’énoncé qu’un cycle de stations ne doit jamais repasser deux fois par la même station ?

 #13 - 25-01-2017 08:44:32

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

merroptimal

@Franky1103: Oui, c'est trivial que sans contrainte de ne pas repasser par la même station une seule ligne (même pas besoin de 2) peut faire tous les segments, et donc à elle seule garantir de desservir tout à tout en un seul arrêt (même pas besoin de 2). Donc en effet oui, une ligne est un cycle qui ne contient chaque station au maximum qu'une seule fois smile

 #14 - 25-01-2017 15:55:46

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 429

Metoptimal

C'est impossible pour 16 ou 17 sommets.

Remarquons déjà que s'il existe un sommet de degré 2, les deux sommets auxquels il est relié ne peuvent eux-même être reliés qu'à 3 autres sommets chacun, aussi il y a au plus 1+2+3*2=9 sommets dans le graphe.

Tous les sommets sont donc de degré 4 (chaque station est parcourue par les deux lignes de métro).

Ensuite, je suis allé faire un tour sur cette page : https://fr.wikipedia.org/wiki/Lexique_d … es_graphes

On cherche un graphe 4-régulier (tous les sommets sont de degré 4), et de diamètre 2 (la distance maximale entre deux sommets est 2) ; le graphe doit aussi être décomposable en deux cycles disjoints, élémentaires et même hamiltoniens (les deux lignes de métro), mais ceci n'est pas nécessaire pour conclure.

Sur ce lien : http://ijact.org/volume4issue5/IJ0450003.pdf il y a une démonstration du fait qu'il n'existe pas de graphe 4-régulier de diamètre 2 à 17 ou 16 sommets. C'est un peu lourdingue comme démonstration (il y a plein de petites étapes), l'anglais n'est pas très bon et le formalisme exagéré, mais ça marche.

Enfin, si j'en crois le titre de cet article, il a été démontré qu'il n'y a qu'une solution pour 15 sommets :

H. J. Broersma, A. A. Jagers, The unique 4-regular graphs on 14 and 15 vertices
with diameter 2, Ars Combinatoria 25 (C) (1988) 55–62.

Je suppose que ça peut se démontrer avec des arguments du même type que pour 16 et 17. Il y a peut être plus élégant.

 #15 - 25-01-2017 18:59:14

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

etroptimal

@Ebichu:
http://data.photofunky.net/output/image/1/6/7/3/167322/photofunky.gif

 #16 - 27-01-2017 18:06:50

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

metrootimal

Avec deux lignes, je ne fais pas mieux que six stations,   sad   sachant qu'avec une seule, on est déjà à cinq.

 #17 - 28-01-2017 11:15:19

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,633E+3

Mteroptimal

Effectivement, mauvais raisonnement pour 11 car les trajets ne sont pas orientés, une ligne c'est deux voies...

Et donc, la limite extrème théorique devient 17 : ça parait difficile à atteindre.

16 est peut-être vraisemblablement possible, mais je ne trouve que pour 15 pour l'instant...

http://www.prise2tete.fr/upload/gwen27-metro15.png

 #18 - 29-01-2017 17:22:38

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1383
Lieu: Coutiches

Metrotpimal

Salut !

Très intéressant comme problème. J'ai trouvé 9 villes... (j'ai laissé mes 1ers essais avant d'arriver à ce résultat)

Je ne sais pas si on peut faire mieux...

http://www.prise2tete.fr/upload/golgot59-villes.jpg

Sur le 1er à 9 villes, on voit bien le principe, sur le second, on visualise mieux le circuit du 2ème métro.

 #19 - 29-01-2017 17:40:52

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1383
Lieu: Coutiches

Metroptimall

En fait voilà mieux avec le même principe : 11 villes

http://www.prise2tete.fr/upload/golgot59-11villes.jpg

Avec cette méthode c'est le max car chaque ville n'est atteignable que par un seul circuit.

Mais peut-être existe-t-il mieux autrement...

 #20 - 30-01-2017 11:25:46

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

metroptimak

http://www.prise2tete.fr/upload/Franky1103-Metro.png
Avec le réseau à 11 villes de golgot59, on ne profite pas de la possibilité de deux trajets longs. Voici ce que cela donne avec un réseau à 13 villes:
a-b / a-b-c / a-i-d / a-f-e / a-f / a-f-g / a-i-h / a-i / a-i-j / a-f-k / a-m-l / a-m
Mais est ce l’optimum ?
Avec le réseau à 15 villes de gwen27, sauf erreur de ma part, on ne n’arrive pas à passer de 1 à 7 ou de 1 à 11 au moins de 3 arrêts.
Par symétrie par rapport aux stations qui peuvent toutes être le point de départ, le réseau devra certainement être en forme de rosace régulière.

 #21 - 30-01-2017 11:51:09

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

Metoptimal

@Franky1103: pour le réseau de gwen 1-15-7  1-15-11.
@tout le monde: Merci à tous les participants, il y a au moins la solution de ebichu qui à tête validée par excel, et il semble y avoir des preuves que 16 et 17 ne sont pas possibles. Bravo donc à ceux ayant trouver une solution valide avec 15 villes!

 #22 - 30-01-2017 12:58:03

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,633E+3

merroptimal

Mon réseau fonctionne.

Sous forme de matrice :
0    1    0    0    1    0    0    0    0    0    0    1    0    0    1
1    0    1    0    0    1    0    0    1    0    0    0    0    0    0
0    1    0    1    0    0    0    0    0    0    1    0    1    0    0
0    0    1    0    1    0    0    1    0    0    0    0    0    0    1
1    0    0    1    0    1    0    0    0    1    0    0    0    0    0
0    1    0    0    1    0    1    0    0    0    0    0    1    0    0
0    0    0    0    0    1    0    1    0    0    1    0    0    0    1
0    0    0    1    0    0    1    0    1    0    0    1    0    0    0
0    1    0    0    0    0    0    1    0    1    0    0    0    1    0
0    0    0    0    1    0    0    0    1    0    1    0    0    1    0
0    0    1    0    0    0    1    0    0    1    0    1    0    0    0
1    0    0    0    0    0    0    1    0    0    1    0    1    0    0
0    0    1    0    0    1    0    0    0    0    0    1    0    1    0
0    0    0    0    0    0    0    0    1    1    0    0    1    0    1
1    0    0    1    0    0    1    0    0    0    0    0    0    1    0


La matrice au carré :
4    0    1    2    0    2    1    1    1    1    1    0    1    1    0
0    4    0    1    2    0    1    1    0    1    1    1    2    1    1
1    0    4    0    1    2    1    1    1    1    0    2    0    1    1
2    1    0    4    0    1    2    0    1    1    1    1    1    1    0
0    2    1    0    4    0    1    1    1    0    1    1    1    1    2
2    0    2    1    0    4    0    1    1    1    1    1    0    1    1
1    1    1    2    1    0    4    0    1    1    0    2    1    1    0
1    1    1    0    1    1    0    4    0    1    2    0    1    1    2
1    0    1    1    1    1    1    0    4    1    1    1    1    1    1
1    1    1    1    0    1    1    1    1    4    0    1    1    1    1
1    1    0    1    1    1    0    2    1    0    4    0    2    1    1
0    1    2    1    1    1    2    0    1    1    0    4    0    1    1
1    2    0    1    1    0    1    1    1    1    2    0    4    0    1
1    1    1    1    1    1    1    1    1    1    1    1    0    4    0
0    1    1    0    2    1    0    2    1    1    1    1    1    0    4


Leur somme :
http://www.prise2tete.fr/upload/gwen27-matricefinale.PNG

On retrouve l'ordre 4 en diagonale, logique... et 2 trajets en double pour chaque nombre.

Malheureusement, pour des raisons de symétrie, ça ne laisse que 15 liaisons de libres. Il en faudrait 16 pour rajouter un 16e point.
Il est rigolo de voir que je me suis amusé avec un parcours de cavalier pour construire la matrice noire. Je suis presque certain que celle d'ebichu présenterait la même particularité.

 #23 - 30-01-2017 15:06:47

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

metroptimak

@gwen27: Effectivement ton réseau fonctionne: mille excuses. Je ne devais pas être réveillé ce matin ou déjà endormi (je travaille de nuit). Le plus surprenant est que ce n'est pas une rosace régulière.

 #24 - 30-01-2017 22:57:03

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 429

merroptimal

@gwen27 : je ne comprends pas de quel parcours de cavalier tu parles, mais je suis également certain que mon graphe présente la même propriété, car c'est le même que le tien - et pour cause, il n'en existe qu'un seul. C'est d'ailleurs un exercice pas si simple que de démontrer que nos deux graphes sont isomorphes. Je ne connais pas de programme qui fasse ça, alors je l'ai fait à la main avec Geogebra, et ça marche.

 

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 : Pif, Paf 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