Problème des quatre quatre

Le problème des quatre quatre, parfois appelé « puzzle des quatre quatre », est un problème récréatif arithmétique : « Quels sont les entiers naturels que l'on peut écrire en utilisant quatre fois le chiffre quatre et les opérations usuelles ? »

Genèse 
Le jeu est mentionné pour la première fois dans l'ouvrage  édité en 1881 par Richard A. Proctor, un astronome anglais réputé pour avoir dressé une des premières cartes de la planète Mars.

Dans son livre , W. W. Rouse Ball en donne en 1892 une description précise et le présente comme un .

Règles 
Plusieurs variantes du jeu existent, selon les symboles mathématiques qu’on s’autorise, sachant que toutes acceptent bien sûr l’addition (« + »), la soustraction (« − »), la multiplication (« × »), la division (« ÷ ») et les parenthèses :
 avec quatre fois le nombre  et les  élémentaires, il est possible d'obtenir tous les entiers naturels de  à , mais il n'est pas possible d'obtenir  ni  ;
 avec quatre chiffres quatre et concaténation possibles (possibilité d'écrire des nombres formés de chiffres  comme « 44 ») le nombre de solutions augmente  ;
 avec le recours aux factorielles (« n! »), à la racine carrée (« √ »), aux puissances (comme dans 444), on peut aller jusqu'à 74  ;
 avec la virgule en tête de nombre (,4 = 0,4 = 4/10) et la fonction gamma (Γ(), où Γ(n) = (n − 1)!, ainsi Γ(4) = 6), on peut aller bien au-delà.

On accepte parfois la fonction inverse (« 1/n »), la sous-factorielle (notée !n = n!·(1 - 1/1! + 1/2! - 1/3! + 1/4! - ... ±1/n!), la sommation (exemple : ), voire des opérations originales telles que le produit des nombres inférieurs de même parité ("n!!", par exemple 9!! ) ou la somme des nombres inférieurs ("n?", par exemple . La répétition à l'infini de la  peut être acceptée ou non : "," (pour 0,4444… ).

En revanche l’opérateur logarithme n’est pas autorisé, car on peut systématiquement exprimer n'importe quel entier par la formule suivante :

Solutions 
Voici des exemples de solutions pour les 23 premiers entiers naturels, en utilisant des règles classiques. Pour chacun, il existe de nombreuses solutions correctes. Les expressions en bleu s'obligent à ne faire appel qu’à quatre entiers 4 (plutôt que quatre chiffres 4) et aux opérations arithmétiques élémentaires. Celles en italique recourent plusieurs fois au même opérateur.
  0         44 − 44
  1         44 ÷ 44
  2        (44 + 4) ÷ 4!
  3      
  4       −44 + 4! + 4!
  5       (44 − 4!) ÷ 4
  6        4,4 + 4  ×,4
  7         44 ÷ 4  − 4
  8         4,4 − ,4  + 4
  9         44 ÷ 4  − √4
 10    4 ÷√4 + 4 ×√4    (44 − 4) ÷ 4
 11   (4!×√4 - 4)÷ 4    44 / (√4 + √4)
 12       (44 + 4) ÷ 4
 13   (4!×√4 + 4)÷ 4    (4 − ,4) ÷ ,4 + 4    44 ÷ 4 + √4
 14    4 × 4 - 4 ÷√4     4 × (√4 + √4) - √4
 15         44 ÷ 4  + 4
 16        (44 − 4) ×,4
 17        (44 + 4!)÷ 4
 18    4 × 4 + 4 −√4    (44 ÷ √4) − 4
 19    4!−(4 + 4 ÷ 4)   (4 + 4 − ,4) ÷ ,4
 20       (44 − 4) ÷ √4
 21    4!− 4 + 4 ÷ 4    (44 − √4) ÷ √4
 22    4!÷ 4 + 4 × 4     44 ÷ (4 − √4)
 23    4!+ 4 ÷ 4 −√4    (44 + √4) ÷ √4
 24        (44 + 4) ÷ √4
 25    4!− 4 ÷ 4 +√4    (4 + 4 + √4) ÷ ,4
 26    4!+ √4 + 4 - 4
 27    4!+ √4 + (4 ÷ 4)
 28        4!+ 4 + 4 - 4
 29    4!+ 4 + (4 ÷ 4)
 30    4!+ 4 + 4 - √4
 31    4!+ (4! + 4) ÷ 4
 32    

Il est particulièrement difficile de résoudre certains nombres. Ainsi, pour 113, David A. Wheeler a suggéré :

Autre exemple d'utilisation de la fonction gamma : 157 = ((Γ(4)!+4) ÷ 4) - 4!.

Accepter d’utiliser le pourcentage ("%") dans les formules  permet d’accéder à un ensemble bien plus vaste de nombres. Par exemple : 113 = (√4 + (√4 + 4!)%) ÷ (√4)%.

Résolution algorithmique 
Le problème et ses généralisations (cinq 5, six 6, etc.) peuvent être résolus par un algorithme simple, qui fait appel à des tables reliant entiers naturels et expressions à base du chiffre choisi. Une telle table existe pour chaque nombre n d’occurrences de d. Par exemple, si d=4, la table pour deux occurrences de d contiendra notamment la paire (8 ; 4+4) ; celle pour trois occurrences de d contiendra la paire (2 ; (4+4)/4), etc. Les tables pour n=1 et n=2 contiennent les formules élémentaires, qui ne sont pas la combinaison de formules plus petites. Ainsi, pour n=1 :
        T[4]    := 4
        T[2]    := √4
        T[4/10] := .4
        T[4/9]  := .4...
        etc.

et pour n=2 :
        T[44] := 44
        etc.

La tâche consiste alors à se référer par récurrence à ces tables, en partant de n=1 jusqu’à dans notre exemple n=4. Pour un n donné, on construit la table en recensant les combinaisons pertinentes de formules plus petites.

Variantes

Extrait de la table des solutions du problème des cinq 5 
 139 = (((5+(5/5))!/5)-5)
 140 = (,5*(5+(5*55)))
 141 = ((5)!+((5+(5+,5))/,5))
 142 = ((5)!+((55/,5)/5))
 143 = ((((5+(5/5)))!-5)/5)
 144 = ((((55/5)-5))!/5)
 145 = ((5*(5+(5*5)))-5)
 146 = ((5)!+((5/5)+(5*5)))
 147 = ((5)!+((,5*55)-,5))
 148 = ((5)!+(,5+(,5*55)))
 149 = (5+(((5+(5/5)))!+5))

Extrait de la table des solutions au problème des six 6
La notation ,6... représente ici le nombre 2/3, avec 6 en décimale récurrente.

 241 = ((,6+((6+6)*(6+6)))/,6)
 242 = ((6*(6+(6*6)))-(6/,6))
 243 = (6+((6*(,6*66))-,6))
 244 = (,6...*(6+(6*(66-6))))
 245 = ((((6)!+((6)!+66))/6)-6)
 246 = (66+(6*((6*6)-6)))
 247 = (66+((6+((6)!/,6...))/6))
 248 = (6*(6+(6*(6-(,6.../6)))))
 249 = (,6+(6*(6+((6*6)-,6))))
 250 = (((6*(6*6))-66)/,6)
 251 = ((6*(6+(6*6)))-(6/6))

Autres puzzles similaires 
On peut concevoir d’autres variantes du jeu en remplaçant le quatuor de 4 par tout autre ensemble de chiffres, par exemple ceux qui composent une année de naissance : 1, 9, 6 et 5 pour 1965.

Références

Casse-tête