Ceux qui me connaissent bien le savent, j’adore me casser la tête sur une foule de « petits » problèmes (mathématiques, algorithmiques ou autres) : ça permet de garder le cerveau en forme et ça me donne une occasion de faire du Smalltalk et de me garder à jour dans mes skills autant de programmation que d’analyse.
Si vous êtes comme moi, voici une liste de ces petits casse-tête qui m’amusent en ce moment (ou depuis un bout) et qui pourrait vous servir de suggestions…
Les nombres de Lychrel
Avant tout, un peu de vocabulaire!
Un palindrome est une mot, une phrase ou un nombre qui s’écrit de la même façon à l’endroit et à l’envers. Par exemple, Laval, Bob ou 17371. Ça peut également être une phrase ou un bout de texte comme « Mon nom » ou le célèbre « A man, a plan, a canal: Panama ».
Grosso modo, un nombre de Lychrel est un nombre qui ne peut pas former de nombre palindrome lorsqu’on l’additionne à répétition avec son « inverse ».
Par exemple, 59 n’est pas un nombre de Lychrel puis qu’on aboutit à un palindrome au bout des itérations suivantes:
59 + 95 = 154
154 + 451 = 605
605 + 506 = 1111
L’histoire devient passionnante quand des mathématiciens se sont intéressés au plus petit nombre pour lequel on n’a pas encore trouvé de nombre palindrome après une quantité anormalement élevée d’itérations. Il s’agit de 196.
Le problème est fascinant en soi de par la simplicité des opérations impliquées (des additions et la détection de palindrome) et les raccourcis et astuces nécessaires (autant mathématiques qu’algorithmiques) pour tenter de le résoudre.
Parmi les incontournables sur le sujet, il y a les sites de Jason Doucet et celui de Wade VanLandingham.
Le site What If?
Un site de questions absurdes avec des explications sérieuses et scientifiques. Un challenge pour le cerveau quand on essaie de formuler une réponse aux problèmes présentés! Ce qui est intéressant, c’est le raisonnement et les arguments des réponses à des problèmes aussi hypothétiques que, bien souvent, idiots! Comme celui-ci par exemple.
La persistence multiplicative
On définit grossièrement la persistence multiplicative par le nombre de fois qu’on peut multiplier les chiffres d’un nombre entre eux jusqu’à ce que le résultat ne comporte qu’un seul chiffre.
Par exemple:
679 -> 6 * 7 * 9 = 378
378 -> 3 * 7 * 8 = 168
168 -> 1 * 6 * 8 = 48
48 -> 4 * 8 = 32
32 -> 3 * 2 = 6
On dira donc que le nombre 679 a une persistence multiplicative de 5.
À ce jour, nous ne connaissons aucun nombre en deça de 10^233 (10 à la puissance 233) ayant une persistence multiplicative supérieure à 11. C’est précisément cette limite qui intéresse les mathématiciens!
Évidemment, ce qu’il est intéressant de chercher ce sont les nombres dits candidats. Tout nombre comportant un 0 est éliminé d’office (ça occasionne forcément un résultat de zéro). Comme la multiplication par 1 n’apporte rien de plus, on ne considérera que les nombres sans le chiffre 1. De plus, on éliminera les nombres comportant à la fois le chiffre 5 et un nombre pair comme cela produira un multiple de 10, donc un résultat de zéro.
Pour un bref aperçu de la persistence multiplicative, il y a une page de Wolfram sur le sujet. Pour un résumé des optimisations et trucs possibles, il y a ce papier.
La conjecture de Collatz
Un autre problème mathématique non résolu : la conjecture de Collatz (aussi appelée conjecture de Syracuse).
Si vous avez quelques cycles de CPU à partager, il existe un projet BOINC juste ici.
Autrement, je vous recommende de lire sur le sujet. Les diverses astuces pour accélérer les calculs sont aussi surprenantes qu’efficaces!
Euler Project
Un site qui propose des problèmes mathématiques à être résolus par ordinateur! Il y a un hic! Il devient assez rapidement évident que la solution est bien souvent (pour ne pas écrire toujours) algébrique et mathématique.
C’est ce dont je me suis encore rendu compte récemment, en scrappant toute une nuit à faire des calculs pour résoudre le problème 131!
Sudoku
Il y a tant d’articles sur le sujet qu’un simple recherche Google devrait suffire à vous tenir occupé en lecture jusqu’à la fin des temps!
Pour ma part, par pur amusement, je me suis attardé à résoudre ces petits problèmes d’une façon surprenante : le préambule, le premier article, la seconde partie et la dernière partie.
Pour un aperçu des techniques de résolution (autres que la force brute), il y a cette liste.
EinStein würfelt nicht!
Communément appelé EWN, ce petit jeu renforme une quantité de particularités contre-intuitives. Autre difficulté, l’aspect probabiliste qui vient tout brouiller les cartes!
Vous pouvez y jouer sur le site de jeux Little Golem si ça vous intéresse. Pour ma part, je planche sur quelques idées de stratégies que j’entends bien tester avec un programme bientôt.
Ruzzle
Un petit jeu tout simple! Et pourtant!
J’ai commencé à étudier de plus près le ruzzle comme en témoigne cet article et celui-ci.
Comme je n’ai toujours pas trouvé de grille meilleure que celle de M. Müller, ma quête se poursuit! Des nouvelles pour très bientôt!
L'endormitoire 