L’énigme ferroviaire du chancelier

Le farniente estival, même sur sa fin, se prête bien à la résolution d’énigmes de tout genre. J’emprunte à Walter Thurnherr, chancelier de la Confédération, le problème suivant, publié dans l’édition du quotidien Le Temps du 17 décembre 2015:

«Toutes les gares de la ligne N vendent des billets à destination de toutes les autres gares. Si l’on ajoute quelques stations, il faudra imprimer 46 types de tickets additionnels. Quel est le nombre exact de ces «quelques» stations et combien y avait-il de gares auparavant?»

Un stratège au service du Conseil fédéral
Brillamment élu le 9 décembre 2015 au poste de chancelier de la Confédération, Walter Thurnherr est un expert de l’univers russe et un fan d’énigmes mathématiques. Il tient cette double compétence de sa formation universitaire –diplômé en physique théorique de l’Ecole polytechnique fédérale de Zurich– et de son parcours dans la diplomatie suisse, qui l’a notamment conduit en Russie, en Géorgie, en Ossétie et en Tchétchénie. Il est très au courant de la problématique de la mobilité, ayant assumé la fonction de secrétaire général du Département fédéral de l’environnement, des transports, de l’énergie et de la communication (DETEC) de 2011 à 2015, sous la houlette de la conseillère fédérale Doris Leuthard.

Walter Thurnherr, chancelier de la Confédération (photo Rolf Weiss, 2016).

La solution dans x jours
Si x est le nombre de gares dans la situation de départ, vous trouverez sur ce même site une solution détaillée de cette énigme dans x jours exactement. Bonne chance!

Daniel Mange, 1 septembre 2020

Solution
Bravo à ceux qui ont cherché et félicitations à ceux qui ont trouvé!

Walter Thurnherr a publié le 13 décembre 2015 sur son compte Twitter (@WThurnherr) une solution algébrique détaillée où x est le nombre de stations dans la situation de départ et y est le nombre des «quelques» stations additionnelles:

De façon plus synoptique, on peut dresser un tableau récapitulant diverses valeurs de x, le nombre de gares dans la situation de départ, et des valeurs de x (x-1), le nombre des billets à destination de toutes les autres gares:

x          x (x-1)

8         8.7 = 56

9         9.8 = 72

10       10.9 = 90

11       11.10 = 110

12       12.11 = 132

13       13.12 = 156

14       14.13 = 182

La différence de x (x-1) pour x = 13 et pour x = 11 est égale à 46; nous avons donc trouvé le nombre de stations au départ, soit x = 11, le nombre de stations à l’arrivée, soit x = 13, et le nombre y des «quelques» stations additionnelles, soit y = 13-11 = 2.

Sous forme algébrique, le nombre de billets possibles au départ, avec x stations, est de x(x-1).

Si l’on rajoute y stations supplémentaires, x est remplacé par x+y et le nombre de billets devient (x+y)(x+y-1).

La différence entre ces deux expressions, soit le nombre de nouveaux billets, est égal à 46:

(x+y)(x+y-1) – x(x-1) = 46 ou

 y(y+2x-1) = 46.

Pour que cette relation ait une solution en nombres entiers, y doit être un diviseur de 46, soit 1, 2, 23 ou 46.

Pour y=1, x=23; mais comme l’énoncé du problème parle de «quelques stations» au pluriel, nous éliminons cette variante.

Pour y=2, x= 11, nous retrouvons la solution tabulaire trouvée ci-dessus.

Pour y=23 et y=46, nous obtenons des valeurs négatives pour x; ces deux variantes sont donc éliminées.

Daniel Mange, 12 septembre 2020

 

Vous pouvez vous abonner à ce site en introduisant simplement votre adresse électronique dans la première rubrique de la colonne de droite de ce blog «Abonnez-vous à ce blog par e-mail».

Daniel Mange

Daniel Mange, Vaudois, est électricien de formation, informaticien de profession et biologiste par passion. Professeur honoraire EPFL, il se voue aujourd'hui à son hobby politique, les transports publics, dans le cadre de la citrap-vaud.ch (communauté d'intérêts pour les transports publics). Il y anime le projet Plan Rail 2050 qui vise à relier Genève à Saint-Gall par une ligne à grande vitesse.

22 réponses à “L’énigme ferroviaire du chancelier

  1. 23 stations nécessitent 506 types de tickets.
    Une station supplémentaire, 24 stations en tout, nécessitent 552 types de tickets, 46 de plus.

    1. Tu brûles… mais le chancelier est très précis dans les détails: “quelques stations” est au pluriel, et exclut donc la solution y=1…

  2. Bonjour,

    Si : Nb de types de billets = x(x-1)

    alors : Nb de types de billets + 46 = (x+y)(x+y-1)
    (y = quelques gares supplémentaires, donc “y” doit être un nombre entier positif >= 2)

    donc : x = 23/y – y/2 + 1/2

    Comme “x” doit être un nombre entier positif >= 2, alors l’expression (23/y -y/2)*2 doit être un entier positif impair.
    (23/y -y/2)*2 = 46/y – y
    46 n’est divisible que par :
    1 (mais y < 2) ;
    2 ;
    23 (mais 46/23 -23 <0) ;
    46 (mais 46/46 – 46 <0).

    y = 2

    Donc, je m'attends à recevoir la solution de cette énigme le 12 septembre prochain.

      1. Cher Monsieur Mange,

        Je viens d’envoyer un message à M. Besson pour lui demander la permission de transmettre sa proposition de solution au groupe de programmeurs Prolog auquel j’appartiens. L’un des participants à ce groupe a tenté de résoudre le problème sans y être parvenu et me demande de lui indiquer mes sources. Me permettez-vous, également, de lui faire suivre votre article?

        Avec mes salutations les meilleures entre-temps.

        A. Linden

      2. Merci ! Je suis néanmoins curieux de découvrir d’éventuelles autres manières de résoudre cette énigme.

    1. J’ai soumis votre énigme au groupe de programmeurs Prolog auquel j’appartiens. Voici une première réponse (je vous la transmets dans son texte originel):

      “I admit I don’t understand the problem statement. Say we have exactly three stops, along a line.

      A — B — C

      How many tickets are we selling now? From where to where? Is it:

      A –> B
      A –> C
      B –> C
      B –> A
      C –> B
      C –> A

      or is it something else?”

      Me permettez-vous de lui faire part, en retour, de votre solution (et sans attendre celle de monsieur Mange), dans l’éventualité où elle pourrait le faire avancer dans sa recherche? Il serait en effet intéressant de vérifier si, et comment un tel calcul peut être représenté en programmation logique.

      Pour ma part, n’étant pas mathématicien de formation, je vous avoue que je ne suis pas plus avancé que mon correspondant.

      1. Vous pouvez sans problème utiliser ma solution dans votre recherche. Résoudre l’énigme via la programmation est un défi intéressant !

        Votre correspondant a correctement établi l’énoncé du problème avec l’exemple des 3 stations. C’est un bon départ pour déterminer combien de types de billets il existe en fonction du nombre de stations.

        Cordialement.

        1. Voici les premiers résultats obtenus par les correspondants du groupe Prolog:

          Selon le premier,

          a) si l’on considère ce qu’il appelle la symétrie des billets (the tickets simmetric), on trouve 4 nouvelles gares (auxquelles son programme associe quatre nombres: 14, 10, 91 et 45).

          b) si chaque gare vend des billets dans les deux sens pour toutes les autres gares (If each station sells both directions tickets for all the other stations), on trouve un nombre correspondant de nouvelles gares, soit dans le cas de deux gares ou seulement d’une, selon le nombre initial de gares (So either 2 or 1 new stations are fine, depending on the initial number).

          Il ajoute: “I suspect the sense of the question was the first one.”

          Ce programmeur a obtenu sa solution grâce à un programme complet, très succinct, en Prolog. J’attends sa permission pour publier son code.

          Le second membre du groupe n’a pas fourni de programme exécutable mais s’est basé sur ses connaissances de la théorie des graphes complets. Il se réfère à la table A000217 de “The On-line Encyclopedia of Integer Sequences” (https://oeis.org/A000217) et en particulier au nombre de bords dans un graphe complet d’ordre n, K_n (Number of edges in complete graph of order n, K_n) pour en déduire que le nombre 46 est la différence entre deux des nombres, où chaque nombre représente le nombre de gares. Selon lui, les deux nombres (n) avec la différence appropriée sont 1081 et 1035:

          “So my take is the number 46 is the difference between two of the numbers, where each number represents the number of stations. The two numbers (n) with the proper difference is 1081 and 1035”.

          Il ajoute:

          “However for a K_n graph the connections have no direction but the tickets have a direction, e.g. from A to B would be one edge and from B to A would be another edge, so the relationship needs to account for this. This is easily handled by noting that for each edge in the K_n graph they would need to be doubled so a relationship of 2 needs to be used for the edges in the calculation.”

          Suit un long tableau des graphes (gares (n), graphes complets et listes de différences) dont il déduit que le nombre des gares existantes avant que 1 soit ajouté est de 22:

          “Looking at the Diff list we find 46 when there are 23 stations (n), so the number of existing stations before 1 is added is 22.

          Dans le cas où plus d’une gare est ajoutée, la somme des valeurs dans la liste de différences
          doit se monter à 46 mais aussi avoir la contrainte qu’elles sont consécutives et commencent à une (contrainte) plus grande que le nombre de gares existantes, par exemple 22 + 24 = 46 et donc le nombre de gares existantes est 10 (Also there could be more than one station added in which case the sum of the values in the Diff list need to sum to 46 but also have the constraint that they are consecutive and start at one greater than the number of existing stations, e.g. 22 + 24 = 46 thus the number of existing stations is 10.)

          L’auteur m’a autorisé à publier ses commentaires. Ceux-ci, ainsi que ceux du premier correspondant, aident-ils à mieux comprendre le problème?

          1. Voici le code complet du programme Prolog (avec la permission de son auteur):

            “if you consider the tickets simmetric:

            /**
            :- use_module(library(clpfd)).

            t(0, 0).
            t(N, T) :- N #> 0, N1 #= N – 1, T #= N + T1, t(N1, T1).

            tickets(N, T) :- N1 #= N – 1, t(N1, TN), T #= TN.

            %?- [N, M] ins 0..25, N #> M, tickets(N, TN), tickets(M, TM), TN – TM #= 46.
            %@ N = 14,
            %@ M = 10,
            %@ TN = 91,
            %@ TM = 45 .
            **/

            So, 4 new stations.

            If each station sells both directions tickets for all the other stations:

            /**
            :- use_module(library(clpfd)).

            t(0, 0).
            t(N, T) :- N #> 0, N1 #= N – 1, T #= N + T1, t(N1, T1).

            tickets(N, T) :- N1 #= N – 1, t(N1, TN), T #= 2*TN.

            %?- [N, M] ins 0..25, N #> M, tickets(N, TN), tickets(M, TM), TN – TM #= 46.
            %@ N = 13,
            %@ M = 11,
            %@ TN = 156,
            %@ TM = 110 ;
            %@ N = 24,
            %@ M = 23,
            %@ TN = 552,
            %@ TM = 506 .
            **/
            So either 2 or 1 new stations are fine, depending on the initial number.
            I suspect the sense of the question was the first one.”

            Ce programme peut être exécuté avec SWI-Prolog.

            Un autre programmeur a implémenté “x(x-1)+46 = (x+y)(x+y-1)” comme équation diophantine (“I am going full metal diophantine”: https://en.wikipedia.org/wiki/Diophantine_equation) et obtenu ce résultat:

            ?- use_module(library(clpfd)).

            ?- [X,Y] ins 1..100, X*(X-1)+46 #= (X+Y)*(X+Y-1),
            label([X,Y]), write(X-Y), nl, fail; true.
            11-2
            23-1
            true.

            Son commentaire sur la solution “Original number of stations 10 or 22”:

            “Its not 10 and 22. ”

            Cela vous paraît-il juste?

          2. Les deux programmes indiquent en tout cas les bons résultats pour respecter le nombre de nouveaux types de billets de 46.

            La seule contrainte qu’on aurait pu ajouter est que : N – M >= 2 ou respectivement Y >= 2, afin d’obtenir la seule solution valide (quelqueS stationS supplémentaires).

            Après il y a une erreur d’interprétation de la réponse :
            “Looking at the Diff list we find 46 when there are 23 stations (n), so the number of existing stations before 1 is added is 22.”
            C’est le paramètre M qui indique le nombre initial de stations, et non le N. Ou alors on prend N est on diminue de 1, mais N vaut 24.
            Le nombre original de stations n’est donc pas 10 ou 22, mais 11 et 23.

            Les données TN et TM sont justes.

  3. Au vu de la complexité des diverses réponses reçues, une thèse de doctorat va bientôt s’imposer… Plus simplement, je vous donne rendez-vous au samedi 12 septembre pour une discussion des solutions raisonnables.

  4. Monsieur Besson:

    “Le nombre original de stations n’est donc pas 10 ou 22, mais 11 et 23.”

    C’est bien ce que le second programmeur (voir mon message précédent) a constaté. Entre-temps, il a
    proposé d’autoriser les nombres négatifs pour les faire reparaître:

    “Maybe the wrong 10 and 22 came from omitting the sign.
    If you allow negative numbers, they appear again:

    Jekejeke Prolog 4, Runtime Library 1.4.6

    ?- use_module(library(finite/clpfd)).

    ?- [X,Y] ins -100..100, X*(X-1)+46 #= (X+Y)*(X+Y-1),
    label([X,Y]), write(X-Y), nl, fail; true.
    -22- -1
    -22-46
    -10- -2
    -10-23
    11- -23
    11-2
    23- -46
    23-1
    Yes”

    Monsieur Mange: promis, je m’arrête ici et attends votre réponse, le 12 septembre prochain.

    Avec mes remerciements à tous pour votre intérêt et votre patience.

  5. Il suffit de chercher quelle somme de chiffres continus donne 46…car pour 4 gares par exemple, il faut
    1+2+3 = 6 billets. Les gares additionnelles, par exemple 2 gares en plus, donnent +4 +5 billets. Total +9 dans ce petit exemple.
    Quelle somme de chiffres continus donne 46… théoriquement on pourrait avoir plusieurs solutions…il y en a beaucoup pour 45…mais pour 46, je crois qu’il n’y a que 10+11+12+13.
    Ca veut dire qu’il y a 10 gares sur la ligne et donc 45 arrêts (somme de 1 à 9) … et qu’en rajoutant 4 gares on arrive à 91 types de billets.

    1. Sapristi.. et oublié qu’un billet pouvait être aller retour
      donc avec 2 gares on a 2 billets, avec 3 gares 6 billets (3*2), avec 4 gares 12 billets (4*3)
      avec 23 gares 506 billets (23*22) et 24 gares …552 billets : +46 mais cette solution n’est pas valable.
      La solution est donc: quelle somme de nombres pairs consécutifs = 46
      N’ai trouvé qu’une solution: 11 gares au départ, donc 110 billets (11 * 10) , on rajoute 2 gares donc 13 gares = 156 billets (13*12) : +46

        1. Ne nous aviez-vous pas promis votre solution et la discussion de celles qui ont été proposées, pour hier, samedi 12 septembre? Ce serait portant fort intéressant de connaître votre point de vue.

          Meilleures salutations entre-temps.

          1. La solution promise a été publiée comme promis le samedi 12 septembre 2020 à 11h25 sur le blog en question. Merci pour l’intérêt que vous avez porté à notre énigme.

  6. Je crois qu’on peut résoudre ce problème plus facilement en établissant une tabelle de manière suivante:

    Nombre de gares nombre de tickets

    5 5 x 4 = 20
    10 10 x 9 = 90
    11 11 x 10 = 110 xxxxx
    12 12 x 11 = 132
    13 13 x 12 = 156 xxxxxx

    156 TICKETS MINUS 46 Tickets = 110 Tickets

    Alors : gares principales sont 11 et gares ajoutées sont 13-11=2

    Avec mes meilleurs compliments

Les commentaires sont clos.