Small Fonts Default Fonts Large Fonts

Plus de 2500 récréations et problèmes mathématiques !

Ce site a été créé en souvenir de DIOPHANTE, mathématicien grec, qui nous a laissé de remarquables ouvrages d'arithmétique. L'objectif est de constituer une vaste bibliothèque de problèmes mathématiques avec les énoncés et les solutions classés par thèmes et selon leur niveau de difficulté et de proposer chaque mois plusieurs problèmes à la sagacité des lecteurs qui ont toute latitude pour envoyer leurs réponses.

Avertissement

Tous les problèmes sont identifiés par un niveau de difficulté :

Très facile

Facile

Moyen

Difficile

Très difficile

Variable

 

D'autre part, les problèmes se traitent généralement à la main et sont alors repérés par l'icône

 

Pour faciliter leur résolution, l'ordinateur peut être utile. Dans ce cas, vous verrez apparaître aussi cette icône

 

Quand l'ordinateur est indispensable, l'icône figure seule.

 

Pour avoir accès aux solutions de chaque problème, cliquez sur solution.

 

Les figures et les graphes ont été réalisés grâce au logiciel Declic.

Avertissement
Open/Close
G248. Le billet universel Imprimer Envoyer
G2. Combinatoire - Dénombrements
computer.png calculator_edit.png  

Problème proposé par Michel Lafond

Un coupon est un ensemble de carrés d'un seul tenant connectés par des côtés (autrement dit un polymino) qui est découpé dans le seul billet de 90 écus existant de format 3 x 3 carrés:
image001.gif1) Vérifier qu'avec le billet ci-dessus, on peut payer par coupon toute somme de 1 à 90 écus.
2) Améliorer ce billet pour pouvoir payer par coupon toute somme de 1 à 100 écus.
3) Trouver un billet de format 4 < 4 carrés, qui permet de payer par coupon toute somme de 1 à 1000 écus.


Avril 2010
Claudio Baiocchi a effectué un dénombrement des coupons possibles: 218 découpés dans un billet de dimensions 3 x 3 et 11506 coupons découpés dans un billet de dimensions 4 x 4.Voir: http://www.research.att.com/~njas/sequences/A059525
Dans le cas du billet 3 x 3,les 218 coupons possibles peuvent être tous représentés selon le nombre de cases qu'ils contiennent, de 1 à 9. Voir Billet 3x3 - 218coupons .
De son côté Patrick Gordon a trouvé un billet de format 4 x 4 permettant de payer toute somme de 1 à 1091 écus.
L'auteur du problème Michel Lafond a amélioré le billet 3x3 avec un score maximum de 104 lorsque la colonne ne comporte que des 1 comme dans l'énoncé et un score maximum de 144 lorsque les valeurs 1,2,4,5 et 8 sont réparties à l'intérieur d'une croix grecque.
S'agissant du billet 4 x 4, le score maximum de 1494 a été atteint avec la deuxième colonne remplie de 1 exclusivement. Compte tenu du nombre élevé de coupons possibles (11506), il est probable mais non démontré que ce score devrait être amélioré avec une distribution différente des plus petites valeurs du billet. Le problème reste donc ouvert.

Mai 2010
Jean Nicot a écrit un programme en langage C# qui donne en une fraction de seconde le score maximum d'un billet dont on donne les valeurs des 16 carrés. Il améliore ainsi de façon significative le score maximum qu'il porte à 1848 avec le billet 4 x 4  suivant:
6    2    124    376
4    1     28    251
5    1     55     28
7    1     76    883
Son programme ticket peut être téléchargé puis exécuté.Il est valable aussi bien pour les billets 3 x 3 que pour les billets 4 x 4.
Si l'on a des difficultés pour l'exécuter, on ouvre les propriétés du programme avec un clic droit de la souris. Il suffit alors de cocher  la case "Débloquer".
Jean Nicot laisse entendre que le score de 1848 peut à nouveau être amélioré. Avis aux amateurs. Le problème reste donc toujours ouvert.

Mai 2010
L'énigme continue à passionner nos lecteurs. Un grand bond en avant a été brillamment accompli par Franck Vivien qui a mis au point un algorithme génétique et a obtenu respectivement les scores de 165 avec le billet 3x3 (contre 144 auparavant) et de 4021 avec le billet 4x4 (contre 1848 auparavant). On lira avec intérêt la note de présentation de son algorithme dans laquelle sont décrits les coupons permettant d'obtenir ces scores. Les lecteurs avisés qui jonglent avec Unix et Galib pourront compiler le code source qu'il a joint à sa note. Selon Franck Vivien, le problème reste ouvert mais nous avons le sentiment que la porte est désormais très étroite....

Septembre 2010
La saga du billet universel n'est pas achevée. En juin dernier, un grande amélioration avait été apportée par Franck Vivien qui à partir d'un algorithme génétique avait obtenu respectivement les scores de 165 avec le billet 3x3 (contre 144 auparavant) et de 4021 avec le billet 4x4. Nous avions annoncé un peu prématurément que la porte semblait très étroite pour améliorer le score de la grille 4x4. Julien de Prabère a relevé le défi en portant le score de cette grille à 4443. Bravo! Et que la saga continue...

Novembre 2010

La balle est reprise au bond par Franck Vivien qui nous écrit : J'ai amélioré l'algorithme génétique que je vous avais soumis au mois de juillet en conditionnant un peu la création aléatoire d'un billet 4x4: au lieu de tirer au sort la position d'une cellule puis sa valeur, je "force" l'algorithme à remplir les cellules dans l'ordre suivant: 5, 4, 0, 1, 6, 10, 9, 2, 3, 7, 8, 12, 13, 14, 15, 11 (en numérotant les cellules de gauche à droite et de haut en bas 0, 1, 2, 3, etc...). Cet ordre a été défini de manière empirique en essayant de remplir le billet autour du "1", et rien n'indique qu'il n'en existe pas de meilleur.
Cette démarche a bien fonctionné puisque l'algorithme m'a fourni plusieurs solutions dont le score dépasse la valeur de 4500, le record étant détenu par le billet suivant (Score 4926):
6      4      28     42
2      1       3     14
101    3      21    1403
300  199     698    2101

Janvier 2011

La balle traverse les Pyrénées et c'est Pedro Pereira du Portugal qui nous écrit:
I used a modified simulated annealing procedure and ended up improving the solution to 5395.
45   30    1    3
15    7    8    2
211    7  104  754
321  110 1509 2268
In order to come up with this solution I had to greatly improve the speed of my checking procedure from 1000 checks/s to about 11500 checks/s (on a 2GHz Athlon 64) by using SSE2.

G248-solution en format pdf

 
RSS 2.0 Our site is valid CSS Our site is valid XHTML 1.0 Transitional