Nombre magique (solution)

Voici comme promit la solution à mon énigme. Comme je vous l’ai dit, je suis passé par l’écriture d’un petit script en C# pour résoudre mon problème. Il m’a fallu parcourir de façon optimisée la liste de tous les nombres possibles.

  1. Parcourir les nombres entre 123456789 et 987654321. Ce qui fait :
    987654321-123456789=864197532 possibilités.
  2. Vérifier que le nombre ne contient pas de zéro.
  3. Vérifier que le premier chiffre est un multiple de 1, que les deux premiers sont multiple de 2, etc.
  4. Puis vérifier qu’il n’y a pas de chiffre en doublon.

J’ai donc commencé par écrire un petit algorithme en français sur le papier pour savoir comment écrire mon code.

Ma solution

Nombre magique

Algorithme pour trouver le nombre magique.

Et voilà le code en C# :

      Console.WriteLine("Calcul du nombre magique...");

      int j;
      bool ok = true;

      // Je parcours tous les nombres parmi lesquels les nombres possibles se trouvent
      for (double i = 123456789; i < 987654321; i++)
      {
        // Je prétend que i est pour l'instant éligible.
        ok = true;

        j = 1000000000;

        // Je parcours la liste des chiffres du nombre.
        for (int k = 1; k <= 9; k++)
        {
          j /= 10;

          // Vérifie s'il n'y à pas de zéro dans le nombre en le parcourant de gauche à droite.
          for (int l = 1; l <= 100000000; l *= 10)
          {
            // Si le reste de la division par 10 des chiffres à gauche est de zéro alors le nombre contient un zéro.
            if ((Math.Truncate(i / l) % 10) == 0)
            {
              // C'est pas bon.
              ok = false;
              // Je remplace le 0 par un 1.
              i += l;
              Console.SetCursorPosition(0, 1);
              Console.ForegroundColor = ConsoleColor.Red;
              Console.WriteLine("Pas bon : {0:D} (contient zéro).", (int)i);
              // Je quitte la boucle.
              continue;
            }
          }

          // S'il y avait un zéro, je passe au nombre suivant.
          if (!ok)
          {
            continue;
          }

          // S'il n'y avait pas de zéro.
          if (ok)
          {
            // Je vérifie si le reste de la division des chiffres sur la gauche par le nombre de chiffres est différent de zéro.
            if ((Math.Truncate(i / j) % k) != 0)
            {
              // Le nombre n'est pas le bon.
              ok = false;
              // J'incrémente le chiffre qui ne correspond pas.
              i += j / 10;
              Console.SetCursorPosition(0, 1);
              Console.ForegroundColor = ConsoleColor.Red;
              Console.WriteLine("Pas bon : {0:D} (mauvais nombre).  ", (int)i);
              // Je passe au nombre suivant.
              continue;
            }
          }
        }

        // Si le nombre semble correspondre aux critères, je vérifie si un des chiffres n'est pas en double.
        if (ok)
        {
          // J'initialise un tableau pour me souvenir quels sont les nombres déjà présent.
          bool[] flags = new bool[9];

          // Je transforme le nombre en chaîne de caractères pour pouvoir la parcourir.
          string resultat = ((int)i).ToString();
          int nb;

          // Pour chaque chiffre dans le nombre à tester.
          foreach (char cnb in resultat)
          {
            // Je récupère ce chiffre.
            nb = Convert.ToInt32(cnb.ToString());

            // Si le chiffre n'est pas marqué dans mon tableau, je le marque.
            if (!flags[nb - 1])
            {
              flags[nb - 1] = true;
            }
            else // Si le chiffre est déjà présent dans mon tableau, c'est qu'il y a un doublon.
            {
              // C'est pas bon.
              ok = false;
              Console.SetCursorPosition(0, 1);
              Console.ForegroundColor = ConsoleColor.Red;
              Console.WriteLine("Pas bon : {0:D} (nombre en double).", (int)i);

              // Je passe au nombre suivant.
              continue;
            }
          }
        }

        // Si finalement le nombre trouvé répond à toutes les conditions. C'est le bon !
        if (ok)
        {
          Console.SetCursorPosition(0, 1);
          Console.ForegroundColor = ConsoleColor.Green;
          Console.WriteLine("Et le nombre magique est : {0:D}.", (int)i);
          Console.Beep(392, 1600);
          break;
        }
      }

      // Au cas où il y aurai eu une erreur dans le code et que le nombre magique n'est pas été trouvé.
      if (!ok)
      {
        Console.ForegroundColor = ConsoleColor.DarkRed;
        Console.WriteLine("Aucun nombre n'a été trouvé ! Il doit y avoir une erreur quelque part...");
      }

      Console.ForegroundColor = ConsoleColor.Blue;
      Console.WriteLine("Appuyez sur une touche pour quitter...");
      Console.ReadKey(true);

Donc, pour finir, le plus important :-D, le résultat :

\mathbf{3\,8\,1\,6\,5\,4\,7\,2\,9}

Petite vérification :
\displaystyle \frac {3}{1}=3

\displaystyle \frac {38}{2}=19

\displaystyle \frac {381}{3}=127

\displaystyle \frac {3816}{4}=954

\displaystyle \frac {38165}{5}=7633

\displaystyle \frac {381654}{6}=63609

\displaystyle \frac {3816547}{7}=545221

\displaystyle \frac {38165472}{8}=4770684

\displaystyle \frac {381654729}{9}=42406081


Autre solution

Il existe bien sûr d’autres façons de résoudre ce problèmes, je vais prendre celles publiées par Susie Lanier.

1ère stratégie

Prendre des nombres aléatoires composés des neuf chiffres et vérifier que les critères fonctionnent.

Par exemple, on peut prendre le nombre 123456789.

On vérifie les critères :

  • 1 divise 1
  • 2 divise 12
  • 3 divise 123
  • 4 ne divise pas 1234
    \displaystyle \frac {1234}{4}=308,5

Donc, le nombre 123456789 n’est pas celui que nous recherchons.

Dans cette stratégie, si nous comptons le nombre de possibilités de nombres à neuf chiffres, nous nous rendons compte que nous avons 9!=362880 possibilités. Un peu trop à vérifier. Nous devons donc choisir une autre stratégie.

2ème stratégie

Nous devons réduire le nombre de possibilités.

Premièrement, il faut que les cinq premiers chiffres soient divisible par 5. Donc le cinquième chiffre est forcément 5 (nous n’avons pas le chiffre 0).

Deuxièmement, 2 divise les deux premiers chiffres, 4 divise les quatre premiers chiffres, 6 les six premiers et 8 divise les huit premiers. Donc pour le deuxième, quatrième, sixième et huitième chiffre doit être pair. Nous avons seulement quatre chiffres pair (2, 4, 6, 8). Ces chiffres doivent donc remplir les espaces pairs. Les chiffres impairs (1, 3, 5, 7 ,9) doivent remplir les espaces impairs.

Maintenant que nous avons vu les chiffres à utiliser. Comptons le nombre de possibilités pour chaque emplacement :

4\;4\;3\;3\;1\;2\;2\;1\;1=4!\times4!\times1=576 possibilités. Beaucoup mieux ! Mais il est encore possible de réduire ce nombre de possibilités.

Puisque 4 divise les quatre premiers chiffres, alors les troisième et quatrième chiffres forment un nombre divisible par 4. Les possibilités sont 12, 16, 32, 36, 52, 56, 72, 76, 92, 96. On note que ces nombres se terminent par 2 ou 6. Le quatrième chiffre doit donc être 2 ou 6. De la même façon, vu que les huit premiers chiffres doivent être divisible par 8 et que 4 divise 8, donc 4 doit pouvoir diviser les huit premiers chiffres. Par conséquence, 4 divise le nombre formé par les septième et huitième chiffres. Le huitième chiffre doit donc être 2 ou 6. Ce qui force le deuxième et le sixième chiffre à être 4 ou 8.

Nous avons donc maintenant :

4\;2\;3\;2\;1\;1\;2\;1\;1=4!\times2!\times2!\times1=96 possibilités.

Maintenant, pour faciliter les choses, renommons notre numéro :
\mathbf{a\,b\,c\,d\,5\,e\,f\,g\,h}

Nous savons que

  • \mathbf{b}=4\mbox{ ou }8
  • \mathbf{d}=2\mbox{ ou }6
  • \mathbf{e}=4\mbox{ ou }8
  • \mathbf{g}=2\mbox{ ou }6

Également :

  • 3 divise abc
  • 6 divise abcd5e
  • Donc :
    • 3 divise abcd5e
    • 3 divise d5e

On peut écrire l’équation : \mathbf{d+5+e=3 \times k} k est une partie constante.
\mathbf{d+e=3 \times k-5} avec d et e pairs.

Si k=5 , et 3 \times k-5=10 . Alors \mathbf{d+e=10} . Est-ce la seule valeur de k ?

Deux cas :

  1. \mathbf{d}=2 et \mathbf{e}=8 , \mathbf{g}=9 et \mathbf{b}=4
  2. Ou \mathbf{d}=6 et \mathbf{e}=4 , \mathbf{g}=2 et \mathbf{b}=8

Donc, nous avons comme nombres possibles : \mathbf{a\,4\,c\,2\,5\,8\,f\,6\,h} ou \mathbf{a\,8\,c\,6\,5\,4\,f\,2\,h} .

Cela réduit encore plus notre choix.

Il y a 4!=24 possibilités pour le premier cas et pareil pour le deuxième. Ce qui nous fait 48 possibilités.

Que savons nous de plus :

  1. \mathbf{a+4+c=3 \times m} ou \mathbf{a+8+c=3 \times m} avec m comme constante (a et c sont impaires).
  2. \mathbf{f+6+h=3 \times n} ou \mathbf{f+2+h=3 \times n} avec n comme constante (f et h sont impaires).

Stratégie combinée

Maintenant en tâtonnant, nous découvrons ce que nous cherchons :

\mathbf{d}=6 , \mathbf{e}=4 , \mathbf{a}=3 , \mathbf{c}=1 , \mathbf{f}=2 et \mathbf{h}=9 .

Notre nombre donne donc :

\mathbf{a\,b\,c\,d\,5\,e\,f\,g\,h}\\  \mathbf{3\,8\,1\,6\,5\,4\,7\,2\,9}

Publicités

~ par ILP sur 13 avril 2013.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

 
%d blogueurs aiment cette page :