Le blog-notes mathématique du coyote

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".

Pourquoi les mathématiciens confondent-ils toujours Noël (25 déc.) et Halloween (31 oct.) ?

Les plaques d'immatriculation du canton du Jura sont numérotées de 1 à 60'000 (c'est presque vrai). Dans ce canton, on peut acheter aux enchères les plaques et beaucoup de personnes sont intéressées à avoir comme numéro leur date d'anniversaire avec le jour, le mois et les deux derniers chiffres de l'année, par exemple JU 11259 pour le 1er décembre 1959 (1/12/59) ou le 11 février 1959 (11/2/59). Pour les mois, on ne veut pas de nombres commençant par 0. Par exemple, 10189 sera forcément de 10 janvier (10/1/88) et pas le 1er janvier (1/01/89). Par contre, l'année peut commencer par un 0. Par exemple JU 1101 pour le 1er janvier 2001(1/1/01). Du coup, les numéros anniversaire auront soit 4, soit 5 chiffres.

Parmi les 60'000 plaques de ce canton, combien peuvent représenter la date d'un anniversaire ?

Si vous répondez au hasard à cette question, quelle est la probabilité que vous ayez choisi la réponse correcte ?
A) 25 %
B) 50 %
C) 60 %
D) 25 %

L' Egypt Exploration Society ainsi que l'université d'Oxford se dit que le travail social que permet Internet représente une bonne idée pour tenter d'aider à déchiffrer des anciens manuscrits. Il est donc possible d'aller tenter de comprendre des papyrus de la ville égyptienne d'Oxyrhynchus et découverte à la fin du dix-neuvième siècle. Ces papyrus décriraient la vie courante, un chant liturgique et de la littérature.
Cela vous tente ? Remontez alors vos manches (et surtout votre cerveau) et allez faire un tour sur http://ancientlives.org/

Source : Sur-la-Toile

Si vous avez aimé mes énigmes sur les soeurs Koukouchkina, vous aimerez sûrement le tout nouveau Crypto Défi de T. Guichard, car il en reprend le mécanisme. Je ne peux pas me prononcer sur l'histoire elle-même, puisque je ne me suis pas (encore) lancé dans ce défi.
En tout cas, connaissant le travail que cela demande, je souhaite plein succès à son auteur.

Une encyclopédie en 4 volumes se trouve sur une étagère très bien rangée. Chaque tome contient 500 pages sans compter les couvertures. Un ver grignote les pages de la no 1 à la no 2000.
Combien le ver a-t-il troué de pages (sans compter les couvertures) ?

L’objectif de ce jeu de réflexion est de reconstituer un motif caché sous une grille en s’appuyant sur des indices numériques. Par exemple, dans une grille 10×10, si une ligne est précédée de la série de nombres 2 1 3, il devra à la fin apparaître de gauche à droite sur la ligne un groupe de deux cases noires, suivi d’une case noire isolée, suivie elle-même d’un groupe de trois cases. Le dessin apparaît au fur et à mesure que le joueur noircit des cases.

Jouer sur le site d'Interstices

Voici l'énigme d'aujourd'hui tirée de "365 jeux de logique pour stimuler vos neurones".

Trois amis vont boire un verre dans un bar. Ils doivent payer 2,50 euros pour les trois. Ils donnent donc chacun 1 euro. Le serveur garde 20 centimes d'euro pour lui et leur rend 10 centimes d'euro à chacun. Ils ont donc payé 90 centimes d'euro chacun plus 20 centimes d'euro de pourboire.
3 x 0,90 = 2,70 euros.
2,70 + 0,20 = 2,90 euros.

Où sont passés les dix derniers centimes d'euro ?

Considérons le gardien de prison sadique qui annonce le "jeu" suivant :

Tous les prisonniers (disons qu'ils sont 20) se voient attribuer un numéro, entre 1 et 20. Le premier prisonnier est appelé et se retrouve face à 20 portes, derrière lesquelles sont cachés des numéros (allant de 1 à 20 là encore). Il a droit d'en ouvrir 10 (au maximum) pour retrouver son numéro. S'il n'y arrive pas, tous les prisonniers sont exécutés (lui compris). S'il y arrive, il n'est pas sauvé pour autant car le commandant appelle le second prisonnier, qui se retrouve à son tour devant les 20 portes, et doit lui aussi trouver son numéro... Et ainsi de suite jusqu'au dernier prisonnier.

Les prisonniers commencent à paniquer, car tout le monde doit trouver son numéro pour être sauvé. En raisonnant rapidement, un des prisonniers explique qu'un seul prisonnier aurait 50% de chances d'y arriver. Avec deux, comme ils ont tous les deux 50% de chances, on tombe à 25%, etc. Avec 20 prisonniers, on a environ une chance sur un million de s'en tirer. Il existe pourtant une stratégie qui donne environ une chance sur trois de tous s'en sortir et accessoirement, cette probabilité ne dépend pas du nombre de prisonnier.

La solution se trouve dans le billet MacGyver et la théorie des groupes.

Source : Owlydays

Le concours ASRO est réservé aux étudiant(e)s des gymnases de Suisse.
L'ASRO encourage les étudiant(e)s à implémenter un modèle ou un programme informatique visant à trouver la meilleure solution. Néanmoins une recherche «manuelle» est également admise. Seules les réponses reçues dans les délais (6 juin 2010) seront prises en considération.

Dans "Enigmes sur les Carrés Magiques", article publié dans le Dossier Pour La Science N°59 (avril-juin 2008, pages 22-25), Christian Boyer offre 100 euros + une bouteille de champagne pour chacune de ces 5 premières énigmes. Une année plus tard dans le site Pour La Science, les 5 mêmes énigmes sont republiées (avril-mai 2009) et une 6ème énigme est ajoutée (juin 2009).

Page des énigmes : www.multimagie.com/Francais/Enigmas.htm