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-10-2024 15:50:21

Spirou
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 489

Réseau efrroviaire non monocéphal

Bonjour,

En prenant le train, je me posais la question suivante:

On considère N villes. On peut relier certaines d'entre elles par des trains.
La distance entre deux villes est définit comme étant le nombre minimum de trains qu'il faut prendre pour aller de l'une à l'autre.

Le but est de construire un réseau ferroviaire tel que:

-La distance maximale séparant deux villes soit 3.

-Pour toute ville [latex]A[/latex], il existe une ville [latex]B[/latex] telle que la distance entre [latex]A[/latex] et [latex]B[/latex] est de 3. (Il n'y a pas de ville plus centrale que les autres).

Si [latex]N \leqslant 5[/latex], la deuxième condition ne peut pas être vérifiée.
Est-ce que pour un [latex]N \geqslant 6[/latex] un tel système ferroviaire existe toujours?

Bon week-end! smile

  • |
  • Répondre

#0 Pub

 #2 - 25-10-2024 17:39:13

Migou
Expert de Prise2Tete
Enigmes résolues : 17
Messages : 546
Lieu: Ville 2/N près 2*i

réseau ferrobiaire non monocéphal

Bonjour Spirou !

Une énigme imaginée dans un train ! Ca lui donne du charme.

Bon, désolé, je vais commencer par bourriner. si je crée un anneau de 6 points ABCDEFA, comme on le voit la propriété est respectée :
- tout point joignable par 3 trajets maxi
- pour tout A il existe B à une distance de 3

maintenant, si je crée une ville G1 reliée à A et à F, puis G2 toujours reliée à A et F, etc.

J'obtiens une structure qui respecte toujours l'énoncé, car Gi est à 3 cases de A et de F et tous les autres points sont joignable plus rapidement. Notamment Gi-Gj se fait en deux trajets.

 #3 - 25-10-2024 18:17:33

Migou
Expert de Prise2Tete
Enigmes résolues : 17
Messages : 546
Lieu: Ville 2/N près 2*i

Réseau ferroiaire non monocéphal

Plus joli et plus dans l'esprit égalitaire de la question, je vous présente le superprisme

http://www.prise2tete.fr/upload/Migou-Superprisme.jpg

il s'agit de P pentagones. chaque colonne de points forme une clique (c'est-à-dire que tous les points sont reliés en direct).

On peut augmenter le nombre P de niveaux  autant qu'on veut, du moment qu'on est pret à maintenir P(P-1)/2 liaisons directes pour chaque colonne.

Pour répondre à la question pour tout entier N, il me semble possible d'ajouter un dernier niveau incomplet (du simple point au quadrilatère)

 #4 - 25-10-2024 19:42:52

aunryz
Expert de Prise2Tete
Enigmes résolues : 17
Messages : 912
Lieu: Nicastro / Tronville

Résea ferroviaire non monocéphal

Est-ce que par hasard la parité ne jouerait pas un rôle ?

Sur un cercle avec une ligne joignant une ville à la N +4
si N est pair, je crois que ça colle.

Merci pour cette énigme topo logique.


Lélio Lacaille - Du fagot des Nombreux

 #5 - 25-10-2024 20:50:31

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

Rseau ferroviaire non monocéphal

Il suffit de construire 3 ensemble de villes toutes reliées entre elles avec un graphe complet dans chaque ensemble.

Et une ville de chaque ensemble est reliée à une de chaque autre.
Ta définition de "centrale" est tout de même très très vague....

Les trajets rouges sont non indispensables, de même que le côté "symétrique du dessin et de la répartition des villes. Il suffit d'avoir au moins 2 villes par graphe complet, la forme la plus simple donnant un hexagone.

Toutes les villes sont distantes les unes des autres de 1, 2 ou 3. Les villes de même couleurs ne peuvent être reliées que par un trajet de longueur 3.
http://www.prise2tete.fr/upload/gwen27-graphetrain.jpg

 #6 - 29-10-2024 19:11:08

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

réseau ferroviairr non monocéphal

Je cherche l'intérêt de proposer une énigme sans aucun suivi, ni commentaire.
Les réponses apportées correspondent elles au problème envisagé ?

 

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 : Pim, Pam et ?

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