Problème 1013
La calculatrice de l'agent 007 possède une "étoile", la touche *, qui effectue une opération secrète. Cette opération possède les propriétés suivantes pour tous les entiers naturels a et b :- 0 * (a + 1) = (0 * a) + 1
- (a + 1) * (b + 1) = (a * b) + 1.
- 1A. Quel est le plus petit entier d supérieur à 287 tel qu'il existe un entier c inférieur à d vérifiant
c * d = c × d ?
- 2A. Quel est l'entier naturel e supérieur à 2 017 tel que 2 017 * e = 2 017 × 40 ?
- 3A, ..., 3F. Quels sont les entiers naturels f tels que f * 2 017 = 40 × 2 017 ?
Pour ce problème, le programme écrit implémente les valeurs du résultat de l'opération dans un tableau à deux dimensions (correspondant aux deux opérandes). Il commence par initialiser les valeurs du tableau connues puis explore itérativement les valeurs que l'on peut en déduire grâce aux règles. Pour avoir une exploration efficace, il utilise une liste pour les nouvelles valeurs à explorer (ce qui marche bien ici car un nouveau résultat est déduit d'un seul précédent résultat). Un choix arbitraire est à faire ici concernant la valeur limite des opérandes : même pour des valeurs élevées, le temps reste raisonnables (cela prend une dizaine de secondes jusqu'à 30 000), mais la consommation mémoire devient relativement importante (3.5 Go pour 30 000 par exemple).
Le code est disponible ici.
Le code est disponible ici.
- 1A. Le plus petit entier d répondant à la question est 315.
- 2A. Le seul entier e supérieur à 2 017 tel que 2 017 * e = 2 017 × 40 est 3 190.
- 3A. Le seul entier f dont on soit certain qu'il vérifie f * 2 017 = 40 × 2 017 est 3 996.