Le blog-notes mathématique du coyote

Les défis mathématiques du "Monde", épisode 9... par lemondefr

Les défis mathématiques du "Monde", épisode 8... par lemondefr

Les défis mathématiques du "Monde", épisode 7... par lemondefr

Les défis mathématiques du "Monde", épisode 6... par lemondefr

Les défis mathématiques du "Monde", épisode 5... par lemondefr

Les défis mathématiques du "Monde", épisode 4... par lemondefr

Les défis mathématiques du Monde, épisode 3... par lemondefr

Les défis mathématiques du Monde, épisode 2... par lemondefr

Les défis mathématiques du Monde, épisode 1... par lemondefr
Chaque semaine, un nouveau défi sur le site du Monde.fr.

Lors de sa tournée, le père Noël arrive au manoir de Monsieur Math. En sortant du foyer de la cheminée, il remarque que le plancher est divisé en tuiles hexagonales portant des numéros. Un écriteau près du foyer donne cet avertissement :
« Avis aux intrus et au père Noël, le plancher de cette salle est piégé. Pour vous rendre au sapin, vous devez emprunter uniquement des tuiles dont le produit total donne 22!, les autres tuiles étant des pièges».
Le Père-Noël sait que 22! est la factorielle de 22, soit le produit des entiers de 1 à 22 (1×2×3×4×5×…×21×22), mais il ne sait pas quel chemin prendre. Aidez le père Noël à se rendre au sapin en lui indiquant les cases qu'il doit prendre et sachant qu'il ne peut pas sauter avec son gros sac de cadeaux.

Je ne sais pas si c'est la fatigue de fin d'année, mais j'ai rêvé cette nuit à un problème dont je me demande s'il existe une réponse connue :

De combien de façons peut-on ranger 10 rectangles de dimensions 1x2 dans un grand rectangle de dimensions 4x5 (par exemple) ?
Plus généralement, comment énumérer toutes les manières de ranger des petits rectangles dans un grand (sans tenir compte des symétries) ?

Quelqu'un a une idée ?

Deux chercheurs américains sont parvenus à mettre au point un algorithme mathématique qui permet de résoudre tous les sudokus, très rapidement et sans avoir à réfléchir ou observer la grille de chiffres.
5, non... 6 ou 3 ? ou 2 ? Depuis plusieurs années, le sudoku a fait une entrée en force dans les journaux. Alors que ceux-ci publiaient autrefois des mots croisés pour divertir leur lectorat, aujourd'hui, bon nombre d'entre eux ne jurent plus que par ces jeux en forme de grille. Le principe est simple : dans la forme classique, il faut remplir toute la grille en plaçant les chiffres de 1 à 9 de telle manière que deux identiques ne se retrouvent pas sur la même ligne, sur la même colonne ou dans le même carré. Pour cela, il faut partir des symboles déjà inscrits et s'adonner à une série de réflexions et de déductions, permettant de placer au fur et à mesure chaque chiffre.
De facile, à moyen puis difficile voire diabolique, il en existe désormais de tous les niveaux. Certains se résolvent ainsi en quelques minutes quand d'autres peuvent prendre plus d'une heure voire plusieurs. Quand on ne parvient pas à le finir, une seule possibilité s'ouvre alors... regarder la solution. Mais des chercheurs de l'université de Notre-Dame aux Etats-Unis ont décidé eux, d'aller chercher plus loin pour résoudre ses casse-têtes chiffrés. En effet, Zoltan Toroczkai et Maria Ercsey-Ravasz ont mis au point un algorithme mathématique capable de résoudre n'importe quel sudoku, très rapidement et sans même avoir à le considérer.
C'est dans le cadre de leurs recherches sur l'optimisation et la complexité informatique que les deux scientifiques se sont intéressés à ce jeu défini en 1979 par l’Américain Howard Garns. Selon eux, les fans de Sudoku utilisent un système de "force brutale" pour résoudre les problèmes, combiné avec un fort processus de déduction. Ils essaient alors tous les combinaisons de chiffres possibles jusqu'à ce que la réponse correcte soit trouvée. Mais si cette méthode est efficace, elle représente une grande perte de temps, estiment les chercheurs plutôt fiers de leur trouvaille publiée dans la revue Nature Physics.

Un nouveau classement des grilles de 1 à 4

A la place, ceux-ci proposent donc d'utiliser leur algorithme universel qui est entièrement déterminant et arrive toujours à la réponse correcte, ceci en bien moins de temps. Au cours de leurs travaux, les chercheurs ont d'ailleurs constaté que le délai nécessaire pour résoudre le problème avec leur algorithme dépendait de la difficulté de la grille attribuée par ses concepteurs. Ils sont ainsi parvenus à développer une échelle de difficulté des problèmes ou des puzzles.
Elle s'étend de 1 à 4 et correspond à peu près à la classification du "facile" à "très difficile" appliquée d'ordinaire. Plus en détail, l'échelle indique notamment qu'une grille de "force" 2 met 10 fois plus de temps à être résolue qu'une de force 1. Ajouté à cela, elle précise également que le puzzle le plus difficile connu aujourd'hui atteint le niveau de 3,6. Mais on ignore aujourd'hui si d'autres grilles encore plus complexes existent.

Savoir jusqu'où l'homme peut aller

"Je ne m'étais pas intéressés au Sudoku jusqu'à ce que l'on commence à travailler plus généralement sur la classe des problèmes SAT" (boolean SATisfiability problem), qui visent à savoir s'il existe une solution à une série d'équations logiques données, explique Toroczkai. "Dans la mesure où le Sudoku fait partie de cette classe, cela semblait être un bon banc d'essai pour notre résolveur, donc je me suis familiarisé avec. Pour moi, et d'autres scientifiques étudiant de tels problèmes, c'est une question fascinante de savoir jusqu'où les hommes peuvent aller en résolvant des Sudokus et sans faire marche arrière, autrement dit sans faire de choix au hasard, en voyant où cela mène et si cela ne fonctionne pas, en recommençant", ajoute t-il.
Reste que pour utiliser l'algorithme des chercheurs, il faut tout de même s'y connaitre un tantinet en mathématiques et qu'au final, les sudokus servent justement à occuper son temps. Quoi de plus satisfaisant que d'achever le remplissage de la grille, après trente minutes d'asticotage mental ? Outre l'intérêt scientifique, pas sûr donc que la résolution instantanée des grilles convainque tant que cela ! Mais les chercheurs estiment que leur algorithme pourrait servir pour résoudre une grande variété de problèmes rencontrés dans l'industrie, l'informatique et même la biologie.

Source : Maxisciences.com

• Lire l'article de Zoltan Toroczkai et Maria Ercsey-Ravasz : The Chaos Within Sudoku
• Lire aussi : The chaos of sudoku, dans Plus Magazine

Le problème se pose simplement et ne nécessite que des accessoires élémentaires :

• Un carré de papier
• Une paire de ciseaux
• Un crayon
• Une règle
• Un compas

La question est de savoir si à l'aide de ces seuls instruments, il est possible de découper un carré en portions... permettant, en les recomposant, de former 3 carrés identiques de plus petites dimensions.

Pour la réponse magnifiquement illustrée, voir le blog Inclassables mathématiques.

Les solutions sont ici

Gary McGuire, mathématicien irlandais, a résolu une énigme datant de plus de dix ans, en découvrant le plus petit sudoku qui existe. Pour cela, il a fallu plus de 7 millions d'heures de calculs sur un superordinateur.
Il n'existe que trois types de sudokus : ceux n'ont qu'une unique solution, ceux qui ont plusieurs solutions et ceux qui n'ont aucune solution. Les premiers sont intéressants, et les autres sont terriblement décevants et ne méritent pas le nom de sudoku (étymologiquement, "chiffre unique").
En général, moins un soduku possède de cases pré-remplies, plus sa complétion sera difficile. De tous les sudokus connus, les plus dépouillés ne comportent que 17 chiffres révélés. Peut-on trouver un sudoku à 16 chiffres ? La question a longtemps été ouverte, jusqu'au 1er janvier 2012. Gary McGuire et deux collaborateurs ont regardé attentivement les 6.7 milliers de milliards de milliards de grilles complètes existantes afin de voir s'il était possible de leur retirer plus de 64 chiffres sans les dénaturer. Leur conclusion : il n'existe pas de sudoku à 16 chiffres.

Pour en savoir plus, lire l'article Pendant ce temps, chez les Sudokus sur l'excellent blog "Choux Romanesco, vache qui rit et intégrales curvilignes".