En préambule, et avant l'explication plus détaillée, je propose de rendre le jeu du "compte et bon" plus intéressant de la façon suivante: on autorise l'ajout d'une opération supplémentaire, qui consiste à pouvoir remplacer à tout moment n'importe quel nombre restant par son carré, et à tirer les nombres à trouver entre 1000 et 9999. L'analyse montre que dans ce cas, plus de 99% des tirages permettent de trouver le compte exact (voir le détail dans l'article), mais les solutions peuvent être bien plus difficiles à trouver, comme on peut le voir dans l'exemple ci dessous, qui présente la façon la plus courte de trouver 862 avec le tirage {1,10,10,25,75,100}.
Opérations Nombres restants
{1,10,10,25,75,100}
10 - 1 = 9 {9,10,25,75,100}
100 x 100 = 10000 {9,10,25,75,10000}
9 x 9 = 81 {81,10,25,75,10000}
10 x 10 = 100 {81,100,25,75,10000}
100 x 100 = 10000 {81,10000,25,75,10000}
10000 + 10000 = 20000 {81,20000,25,75}
75 x 75 = 5625 {81,20000,25,5625}
5625 x 5625 = 31640625 {81,20000,25,31640625}
20000 x 20000 = 400000000 {81,400000000,25,31640625}
400000000 - 31640625 = 368359375 {81,368359375,25}
25 x 25 = 625 {81,368359375,625}
625 x 625 = 390625 {81,368359375,390625}
368359375 / 390625 = 943 {81,943}
943 - 81 = 862 {862}
On pourrait ainsi redonner un peu d'intérêt à un jeu devenu trop facile, et éviter les ex-aequos.
Le compte est bon est un des jeux télévisés les plus anciens à être diffusés dans le monde. Créé en France par Armand Jammot, il a commencé à être diffusé en 1965 dans un autre format (le mot le plus long) avant de connaitre sa forme actuelle en 1972. Un jeu similaire appelé countdown est diffusé depuis 1982 par la télevision britannique (channel 4). Pourtant, bien que ce jeu soit certainement un des plus connus en France comme en Grande Bretagne, il n'en existe aucune étude scientifique sérieuse.
On trouvera
ici un long article (17
pages en anglais et en pdf) qui
fait une présentation extrêmement détaillée du jeu et des différents
algorithmes permettant de le résoudre, ainsi que des statistiques
poussées. Il s'agit d'un preprint dont une version réduite sera
probablement soumise à une conférence ou une revue scientifique, si
j'ai le temps (Mise à jour du 10/2015: une version un peu plus courte de l'article a été acceptée pour publication à
GCAI 2015
et les proceedings sont maintenant
disponibles
dans la série Epic Computing in Computer Sciences).
Il est également disponible sur
arxiv.
Une version html de l'article se trouve
ici. Il est cependant préférable de
lire le pdf, les formules mathématiques sont plus claires..
Cet article introduit un nouvel algorithme utilisant des tables de
hachage qui permet d'améliorer considérablement les temps de
calcul.
Il propose également des voies d'amélioration du jeu,
permettant de le rendre plus difficile et plus intéressant, de
diverses façons. Il est possible par exemple de sélectionner dans une
base de données des problèmes connus pour être difficiles, ou de changer
l'ensemble de tirage des 6 nombres.
Il est également possible d'ajouter aux quatre opérations disponibles
normalement le carré, c'est à dire la possibilité de remplacer un
nombre par son carré. Par
exemple, alors qu'il est impossible de trouver 999 avec 1,2,3,4,5 et 6
cela devient possible en ajoutant le carré à la liste des opérations
autorisées.
Operations Nombres restants
{1,2,3,4,5,6}
3 x 6 = 18 {1,2,4,5,18}
18 x 18 = 324 {1,2,4,5,324}
4 + 5 = 9 {1,2,9,324}
324 + 9 = 333 {1,2,333}
1 + 2 = 3 {3,333}
333 x 3 = 999 {999}
Dans cette variante, le jeu n'est plus forcément décidable car il n'y a pas réduction du nombre d'éléments disponibles à chaque étape. L'article présente d'ailleurs des exemples sur lesquels la décidabilité n'est pas du tout claire. Les résolutions peuvent être extrêmement longues et utiliser des chiffres très élevés. Par exemple, pour trouver 862 avec 1,10,10,25,75 et 100 il faut au minimum 14 étapes, en utilisant des nombres aussi grand que 400000000.
Opérations Nombres restants
{1,10,10,25,75,100}
10 - 1 = 9 {9,10,25,75,100}
100 x 100 = 10000 {9,10,25,75,10000}
9 x 9 = 81 {81,10,25,75,10000}
10 x 10 = 100 {81,100,25,75,10000}
100 x 100 = 10000 {81,10000,25,75,10000}
10000 + 10000 = 20000 {81,20000,25,75}
75 x 75 = 5625 {81,20000,25,5625}
5625 x 5625 = 31640625 {81,20000,25,31640625}
20000 x 20000 = 400000000 {81,400000000,25,31640625}
400000000 - 31640625 = 368359375 {81,368359375,25}
25 x 25 = 625 {81,368359375,625}
625 x 625 = 390625 {81,368359375,390625}
368359375 / 390625 = 943 {81,943}
943 - 81 = 862 {862}
Il reste 49 problèmes qui n'ont pas de solution connue pour cette variante du jeu. Ceci ne signifie pas qu'il n'en existe pas, mais que, avec les bornes numériques du programme, aucune solution n'a été trouvée. Ces 49 problèmes sont les suivants:
1 1 10 10 25 100: 858
1 1 10 10 25 75: 863
1 1 10 10 50 100: 433 453 547 683 773 853
1 1 10 10 50 75: 793 853 978
1 1 10 10 75 100: 433 453 457 478 547 618 653 682 708 718 778 793 822 853 892 907 958 978
1 1 10 25 75 100: 853 863
1 1 10 50 75 100: 793 813 853 978
1 1 5 5 25 100: 813 953
1 1 7 7 50 100: 830
1 1 8 8 9 9: 662
1 1 9 10 10 100: 478 573 587 598
1 1 9 9 10 100: 867
1 9 9 10 10 100: 867 947 957 958 967
Vous pouvez lire l'article pour avoir plus de détails.
Le programme ci-dessous implante l'algorithme standard (sans le carré) pour résoudre le jeu "ordinaire", en proposant toutes les solutions possibles après élimination des solutions "identiques" (voir l'article):
On trouvera ci-dessous le programme utilisé pour générer les statistiques présentées dans l'article. Il permet d'apprécier la rapidité de l'algorithme puisque la version Linux 64 bits sur un core i7 980X génère l'ensemble des solutions et des statistiques en 13s pour le jeu standard (la version 32 bits donne le résultat en 23s; les versions Windows sont un peu plus lentes). A titre de comparaison un site en principe consacré au compte est bon donne un temps de calcul de 60 jours pour calculer toutes les solutions(!), et le site de kitsune donne un temps indicatif de quelques heures de calcul.
Il s'agit d'un programme à utiliser en ligne de commande. Il prend quatre paramètres:
Si l'on tape par exemple sous Windows
stats64.exe 6 100 1000 1000
on va générer les statistiques pour le problème à 6 plaques, en cherchant toutes les solutions entre 101 et 999, et en cherchant toutes les solutions approchées possibles, aussi loin soient-elles (c'est globalement le jeu "classique").
Le programme a été intensivement testé sous Linux en version 64 bits. Les autres versions fonctionnent pour 6 plaques, il n'y a pas de garantie pour le reste (en particulier pour les versions Windows, tout spécialement au niveau de l'allocation mémoire).
Le programme génère trois fichiers de statistiques:
L'article cite un programme écrit en 1986 qui résolvait déjà le jeu en moins de 30s sur AMIGA, le code source se trouve ici et ici; quand à l'exécutable pour amiga, il est là
Le téléchargement ou la reproduction des documents et photographies
présents sur ce site sont autorisés à condition que leur origine soit
explicitement mentionnée et que leur utilisation
se limite à des fins non commerciales, notamment de recherche,
d'éducation et d'enseignement.
Tous droits réservés.
Dernière modification: 09:48, 22/02/2024