Véritable work in progress, le problème du cavalier polygraphe est toujours d'une actualité brûlante. On connaissait déjà le nombre de parcours fermés, ceux qui reviennent à la case de départ, les plus rares. Mais la question du nombre de parcours ouverts restait en suspens… En 2001, le mathématicien uruguayen Ernesto Mordecki était arrivé un premier résultat prometteur mais très incomplet. Depuis, il est revenu à la charge : avec un collègue, ils ont diffusé un travail passionnant sur le sujet. En se basant sur des simulations, ils donnent maintenant une estimation précise du nombre de solutions. Sans tenir compte des symétries, il y aurait autour de 1,22 million de milliards de parcours possibles ! Un nombre qui paraît véritablement astronomique si vous vous êtes frottés à ce casse-tête. Imaginez que vous griffonniez chacune de ces solutions sur une feuille de papier et que vous les empiliez les unes sur les autres : la pile couvrirait la distance terre-soleil…

Le billet précédent parlait d'un texte de Georges Perec. Ca m'a rappelé un jeu célèbre qui l'a beaucoup amusé, le problème du cavalier (aussi appelé polygraphie du cavalier). Les règles sont simples : un cavalier doit parcourir toutes les cases d'un échiquier sans revenir sur une case déjà visitée. Collégien, j'ai passé de nombreuses heures de cours à gribouiller des feuilles quadrillées pour résoudre ce problème. Mais il assez malcommode de devoir gommer les erreurs et les essais infructueux. Je viens donc de finir un problème du cavalier en flash pour faciliter un peu les choses. On sait maintenant qu'il y a largement plus d'un milliard de solutions possibles ! Saurez-vous en retrouver au moins une ? Lire la suite...

On vous a peut-être déjà mis au défi de plier une feuille de papier douze fois de suite. Mais c'est impossible. Essayez pour voir : pliez là en deux, puis à nouveau en deux, etc. Pas moyen d'atteindre ne serait-ce que huit pliages, ce qui nous paraît pourtant être un tout petit nombre. Ca ne semble pas insurmontable si on s'y prend soigneusement. Mais la feuille devient très vite extrêmement épaisse et il est physiquement impossible de replier le petit cube de papier que l'on a entre les mains. Même avec une presse puissante, ce n'est pas une question de force. Et vous n'y arriverez pas plus avec une feuille de la taille d'un panneau publicitaire ou d'un terrain de football. Alors impossible ? Oui et non : Lire la suite...