Takeshi Kitano's problem

Imaginez une file de nombres : 1, puis 2, puis 3, et ainsi de suite. Le défi consiste à les laisser dans cet ordre et à placer entre eux des opérations choisies pour atteindre 2011. On peut additionner, soustraire, multiplier, diviser, prendre une racine carrée, élever à une puissance ou utiliser une factorielle.

Une première formule regroupe les trois premiers nombres, amplifie le résultat avec une puissance, puis compense avec des produits et des additions. La recherche informatique explore les nombreuses parenthèses et opérations possibles afin de trouver une écriture plus courte.

Le problème de Takeshi Kitano est un problème de recherche d'expression arithmétique. Les entiers positifs 1, 2, 3, … doivent apparaître dans leur ordre naturel, tandis que les opérations autorisées et les parenthèses sont choisies pour obtenir exactement 2011. La « longueur » d'une formule doit être définie par la règle de comparaison retenue, par exemple le nombre de caractères ou celui des symboles.

La formule proposée par Kitano utilise un exposant 4 comme notation d'une puissance : (1 + 2 + 3)⁴ vaut 6⁴. Les autres groupes sont des produits consécutifs, puis les nombres 12 et 13 sont ajoutés séparément. La source mentionne aussi la factorielle, notée n!, et la factorielle double, notée n!! ; cette dernière signifie usuellement le produit de n par les entiers positifs de même parité jusqu'à 1 ou 2.

Le cœur du problème n'est donc pas seulement de calculer une valeur, mais d'optimiser une écriture sous des contraintes de syntaxe. Une recherche par ordinateur peut énumérer des expressions, évaluer celles qui sont définies et conserver les plus courtes. La formule courte citée dans la source appelle toutefois une vérification indépendante : avec la convention usuelle, (1 + 2)!! + (3!)⁴ − 5 = 3 + 1296 − 5 = 1294, et non 2011.

Prenons la formule proposée par Kitano, en conservant les entiers dans l'ordre : 1 à 13. Les groupes à évaluer sont (1 + 2 + 3)⁴, 5 × 6 × 7 × 8 et 9 × 10 × 11 ; les termes isolés sont 12 et 13.

D'abord, 1 + 2 + 3 = 6, puis 6⁴ = 1296.
Ensuite, 5 × 6 × 7 × 8 = 1680.
Puis, 9 × 10 × 11 = 990.
Enfin, 1296 + 1680 − 990 + 12 + 13 = 2011.

Le résultat est donc exactement 2011. Un contrôle refaisable consiste à regrouper les termes positifs : 1296 + 1680 + 12 + 13 = 3001, puis à retirer 990 ; on retrouve bien 3001 − 990 = 2011.

Pour résoudre une variante à la main, on peut d'abord repérer les regroupements qui produisent de grandes valeurs, comme une puissance ou un produit. Le geste consiste ensuite à vérifier l'ordre des entiers et la valeur exacte de chaque groupe.

Pour chercher une formule courte, un programme peut générer des expressions et éliminer celles qui utilisent un nombre interdit, changent l'ordre des entiers ou contiennent une division par zéro. Cette méthode devient préférable lorsque le nombre de parenthèses et d'opérations rend l'essai manuel trop vaste.

Pour vérifier une solution annoncée, le critère décisif reste l'évaluation complète de l'expression. Une formule peut sembler plus élégante ou plus courte, mais elle ne répond au défi que si elle donne exactement 2011 selon les conventions annoncées.

Le problème de Kitano ne se confond pas avec un simple calcul de 2011. Dans un calcul ordinaire, les nombres et les opérations sont déjà donnés ; ici, l'expression elle-même doit être construite sous une contrainte d'ordre. Une formule qui atteint 2011 mais qui réordonne les entiers résout donc un autre problème.

Il ne se confond pas non plus avec le seul problème de trouver une expression égale à 2011. La recherche de la formule la plus courte ajoute un objectif d'optimisation : deux expressions peuvent avoir la même valeur, mais celle qui respecte mieux la mesure de longueur retenue est privilégiée.

La contrainte « dans leur ordre naturel » n'autorise pas à permuter 5 et 6, même si une permutation rendait le calcul plus commode. Le symptôme observable est une suite de nombres qui n'est plus croissante ; il faut alors rejeter l'expression ou reformuler la recherche avec une autre règle.

La brièveté n'a de sens qu'après avoir fixé sa mesure. Compter les caractères, les nombres, les opérateurs ou les parenthèses peut produire des classements différents. Il faut donc annoncer la convention avant de qualifier une formule de « plus courte ».

La factorielle double est un piège de lecture. Avec n!! = n × (n − 2) × … jusqu'à 1 ou 2, 3!! = 3 et 3! = 6 ; les deux notations ne sont pas interchangeables. La formule courte reproduite par la source donne alors 1294, ce qui signale une discordance à résoudre avant de la présenter comme solution.

Certaines expressions candidates ne sont pas définies : une division par zéro bloque l'évaluation, et une racine carrée d'un nombre négatif n'est pas réelle. Le programme ou le lecteur doit les écarter, sauf si le domaine de calcul est explicitement élargi.

Le problème ouvre sur une question générale d'optimisation symbolique : comment parcourir un très grand ensemble d'expressions sans perdre celles qui pourraient devenir les plus courtes ? Une recherche algorithmique peut mémoriser les valeurs déjà obtenues et comparer systématiquement les constructions admissibles.

La notion de formule courte rappelle aussi qu'un résultat dépend de son langage. Ajouter une opération, autoriser une constante ou modifier le coût d'une parenthèse change l'espace de recherche et peut changer le gagnant. La longueur n'est donc pas une propriété absolue de la valeur 2011.