Ca y est, j'en ai trouvé qui sont pires que moi. C'est tout à fait le genre de trucs susceptibles de m'amuser, mais là, j'avoue, je n'aurais même pas eu le courage de m'y mettre. Greg Crowther, chercheur à l'université de Washington (qui ne se trouve pas à Washington, mais à Seattle) et Liz Stahl, avocate dans la même ville (Seattle, donc, pas Washington) souffrant, je cite, "d'inhalation chronique de science de seconde main, puisque fille et épouse de biologiste", se sont attelés au comptage des raisins secs dans des boites de céréales.
Intrigués par l'emballage de la boite qui annonçait qu'on y trouvait "deux tasses" de raisins, et ce aussi bien sur les paquets de 400g que ceux de 550 ou 700g, ils en ont ouvert deux de chaque, et ont compté les raisins, afin de déterminer si la taille des "tasses" variait avec le poids du paquet, et surtout de savoir lequel choisir selon que l'on apprécie les raisins ou pas. La conclusion de leur étude, sur un échantillon certes réduit, est que les paquets de 550g sont les mieux dotés, de 0.52 à 0.67 raisins par gramme. Je n'ai pas d'idée précise du poids d'un raisin sec, mais cette proportion me semble énorme (à noter que le paquet s'appelle Raisin Bran - Wikipedia is everywhere ...). L'autre conclusion est que leur étude mérite d'être poursuivie, compte tenue de la disparité observée dans les résultats, pour savoir si les employés de Kellogg's sont suffisamment formés au maniement des tasses, ou bien si l'allocation des raisins dans chaque paquet est en fait complètement aléatoire ...
Un peu plus sérieux, ce billet de Didier Müller sur son blog de maths, indiquant une estimation du nombre de trajets possibles pour un cavalier devant parcourir toutes les cases d'un échiquier sans jamais repasser par la même.
Plus que l'estimation, effectivement énorme, c'est la simplicité de la règle de Warnsdorff utilisée dans l'article cité qui m'a épaté. Parce que ne sais pas si vous avez déjà essayé d'en tracer, des chemins de ce genre, en tout cas moi oui (étonnant, non ?), et je ne suis pas sûr d'y être déjà arrivé, sauf peut-être par le plus heureux des hasards. Pourtant la règle est simple, simplissime même : à chaque mouvement, il faut privilégier les cases qui offrent le moins de possibilités de continuation.
Clair, net, et (presque tout le temps) efficace.
Les machines sont peut-être plus fortes aux échecs, mais avant qu'elles parviennent à énoncer des heuristiques d'une telle limpidité il y a du boulot ...
2 réactions
1 De Vicnent - 08/12/2006, 12:16
Attention à ne pas tout confondre.... limpidité tout ça...
Cette heuristique "à chaque mouvement, il faut privilégier les cases qui offrent le moins de possibilités de continuation" a le mérite d'exister certes, mais si elle fonctionne, c'est parce que le problème est modélisé de la sorte qu'il forme ce qu'on appelle un matroïde (et cette heuristique est appellé Algorithme Glouton : à chaque étape, un choix est fait, et on ne reviendra jamais sur ce choix. Cet algo est optimal si le pb a une strcuture de matroïde). Et de fait, ça fonctionne...
en.wikipedia.org/wiki/Mat...
2 De vicnent - 08/12/2006, 12:28
euh.... d'autre part, ce n'est pas l'estimation du nombre de trajets possibles pour un cavalier devant parcourir toutes les cases d'un échiquier sans jamais repasser par la même case mais du de trajets possibles pour un cavalier devant parcourir toutes les cases d'un échiquier sans jamais repasser par la même case en utilisant la règle de Warnsdorff. (c'est dire le nombre de trajets qu'on s'interdit...)
Il serait amusant de regarder la problème sous la forme d'un pur dénombrement, du fait des très nombreuses permutations qui doivent simplifier le problème (64*4 rien qu'en considérant chaque trajet comme un circuit orienté, et 4 cotés... soit une réduction de de 1/256 après 5 secondes de reflexion.)