En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies pour assurer le bon fonctionnement de nos services.
En savoir plus

Ouverture scientifique

Enigme du mois de décembre 2019

Par JEAN-MANUEL MENY, publié le jeudi 9 janvier 2020 20:59 - Mis à jour le jeudi 9 janvier 2020 21:11
le plan
Les résolutions

Rappel de l'énoncé

Vous trouverez ci-dessous le plan d'une région avec ses villes et son réseau routier.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Saurez-vous définir un itinéraire passant par chaque ville une fois et une seule ?

 

 

Les trouveurs.

L'énigme a été résolue par Clémence Schodts, Camille Place, Dorian Camhi, Clément Arnould,  
Maxime Balleur, Thibault Hervier, Samy Vincent.

 

L'argument de Clémence, Camille, Dorian, Clément,  Maxime.

 

L'argument utilisé par nos chercheurs  est  présenté ci-dessous.

La coloration des villes   de la région ambarroise en rose et des villes de  Game of Thrones en bleu montre que:

  •  partant d'une ville rose, on ne peut que rejoindre une ville bleue,
  •  partant d'une ville bleue, on ne peut que rejoindre une ville rose.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Comme il y a un total de 14 villes, tout chemin passant par chaque ville une fois et une seule sera nécessairement
de la forme R B R B R B R B R B R B R B ou de la forme  B R B R B R B R B R B R B R
(où R désigne une ville rose et B désigne une ville bleue). En d'autres termes, un tel chemin devra alterner  le rose et le bleu, et ainsi passer par autant de villes roses que de villes bleues: 7 roses, 7 bleues.

Un tel chemin ne peut donc pas exister car il n'y a que six villes roses pour huit villes bleues.

 

 

La démarche de Thibault et de Samy

 

Thibault et Samy ont utilisé un programme Python recherchant l'ensemble des chemins.


Le code ci-dessous, suit le principe du code de Thibault.
On l'illustre sur un exemple de carte plus petite avant de faire des tests sur la carte de l'énigme.


Région_1 = {
'1': ['2', '3'],
'2': ['1', '3', '4'],
'3': ['1', '2'],
'4': ['2']
}

def recherche(réseau):
    
    def prolonger(chemin):
        Voisines = [v for v in réseau[chemin[-1]] if v not in chemin]
        if Voisines != []:
            for voisine in Voisines:
                prolonger(chemin + [voisine])
        else:
            les_chemins.append(chemin)
                 
        
    les_chemins = []
    for ville in réseau: prolonger([ville])
    
    return les_chemins 


itinéraires = recherche(Région_1)
for iti in itinéraires:
    print(iti)

 

La région définie dans le code correspond à la carte suivante:

 

 

 

 

 

Et l'affichage obtenu est:


['1', '2', '3']
['1', '2', '4']
['1', '3', '2', '4']
['2', '1', '3']
['2', '3', '1']
['2', '4']
['3', '1', '2', '4']
['3', '2', '1']
['3', '2', '4']
['4', '2', '1', '3']
['4', '2', '3', '1']

Vous constaterez facilement que l'on a bien ainsi tous les chemins non prolongeables et ne passant pas plus d'une fois sur une ville. En particulier, certains de ces chemins passent par toutes les villes. On applique ensuite ce programme à la carte de l'énigme:


Enigme = {
    'Myr': ['Meximieux', 'Douvres', 'Ambronay'],
    'Braavos': ['Meximieux', 'Ambérieu', 'Lagnieu'],
    'Port-Réal': ['Meximieux','Lagnieu',  'Douvres'],
    'Astrapor': ['Meximieux', 'Ambronay', 'Ambérieu'],
    'Vaes-Dothrak': ['Ambronay', 'Leyment', 'Douvres'],
    'Qarth': ['Ambronay', 'Ambérieu', 'Leyment'], 
    'Port-Lannis': ['Ambérieu', 'Lagnieu', 'Leyment'],
    'Meereen': ['Lagnieu', 'Douvres',  'Leyment'],
    'Ambronay': ['Myr', 'Qarth',  'Vaes-Dothrak', 'Astrapor'],
    'Douvres': ['Myr', 'Vaes-Dothrak', 'Port-Réal', 'Meereen'],
    'Meximieux': ['Myr','Braavos', 'Port-Réal', 'Astrapor'],
    'Ambérieu': ['Braavos', 'Astrapor', 'Port-Lannis', 'Qarth'],
    'Lagnieu': ['Braavos', 'Port-Réal', 'Port-Lannis', 'Meereen'],
    'Leyment': ['Port-Lannis', 'Qarth', 'Vaes-Dothrak', 'Meereen' ],
}

 

On trouve plusieurs milliers de chemins.

Parmi ceux-là les plus courts passent par 6 villes.
Par exemple: ['Ambronay', 'Qarth', 'Leyment', 'Meereen', 'Douvres', 'Vaes-Dothrak'].

Et les plus longs passent par 13 villes.
Par exemple:
['Myr', 'Meximieux', 'Braavos', 'Ambérieu', 'Astrapor', 'Ambronay', 'Qarth', 'Leyment', 'Port-Lannis', 'Lagnieu', 'Port-Réal', 'Douvres', 'Vaes-Dothrak'].

Il n'y a donc pas de chemin couvrant les 14 villes sans répétition.

 

Complément travaux publics

 

Camille, Dorian et Samy ont complété leurs réponses en remarquant que la construction de nouvelles routes
rend le problème résoluble.

Sur l'exemple précédent ['Myr', 'Meximieux', 'Braavos', 'Ambérieu', 'Astrapor', 'Ambronay', 'Qarth', 'Leyment', 'Port-Lannis', 'Lagnieu', 'Port-Réal', 'Douvres', 'Vaes-Dothrak'],
il suffirait de construire une route entre Vaes Dothrak et Meereen pour boucler notre visite de toutes les villes.