Factorielles divisibles

Récemment, j'ai été complètement déconcerté par ce tweet de Farm Library:


"C'est ce qui arrive si vous ne multipliez pas mais divisez dans la factorielle."

Quand je l'ai vu, j'ai dû abandonner mon entreprise, prendre un cahier et vérifier la formule. Le projet de résultat semblait logique. Depuis la version multiplicative $$$n!$ avec l'augmentation $$$n$ tend vers l'infini, alors la version "divisante" devrait tendre vers zéro. Et $$$\ frac {n ^ 2} {n!}$ se comporte de cette façon; fonction polynomiale $$$n ^ 2$ croît plus lentement qu'une fonction de puissance $$$n!$ pour assez grand $$$n$ :

$$

$$\ frac {1} {1}, \ frac {4} {2}, \ frac {9} {6}, \ frac {16} {24}, \ frac {25} {120}, \ frac {36 } {720}, \ frac {49} {5040}, \ frac {64} {40320}, \ frac {81} {362880}, \ frac {100} {3628800}$$

Mais pourquoi le résultat de la division prend-il la forme $$$\ frac {n ^ 2} {n!}$ ? D'où ça vient $$$n ^ 2$ ?

Pour répondre à cette question, j'ai dû démanteler l'ancien traumatisme associé à l'étude de la division fractionnaire, mais j'ai fait face à la douleur. En passant de la formule du tweet de gauche à droite, nous obtenons d'abord $$$\ frac {n} {n-1}$ . Ensuite, en divisant cette valeur par $$$n-2$ nous obtenons

$$

$$\ cfrac {\ frac {n} {n-1}} {n-2} = \ frac {n} {(n-1) (n-2)}$$

En poursuivant dans cette voie, on se retrouve avec:

$$

$$n \ mathbin {/} (n-1) \ mathbin {/} (n-2) \ mathbin {/} (n-3) \ mathbin {/} \ cdots \ mathbin {/} 1 = \ frac {n } {(n-1) (n-2) (n-3) \ cdots 1} = \ frac {n} {(n-1)!}$$

Pour obtenir le résultat affiché dans le tweet $$$\ frac {n ^ 2} {n!}$ , nous multiplions simplement le numérateur et le dénominateur par $$$n$ . (Bien qu'à mon goût, l'expression $$$\ frac {n} {(n-1)!}$ plus clair.)

---

Je suis un fan factoriel officiellement reconnu. Gardez vos séquences de Fibonacci avec vous; voici ma fonctionnalité préférée. Chaque fois que j'apprends un nouveau langage de programmation, mon premier exercice consiste à écrire plusieurs procédures de calcul des factorielles. Au fil des ans, j'ai trouvé plusieurs variantes de ce sujet, par exemple, un remplacement dans la définition $$$\ fois$ sur $$$+$ (ce qui nous donne des nombres triangulaires). Mais il semble que je n'ai jamais pensé à remplacer avant $$$\ fois$ sur $$$\ mathbin {/}$ . Cela se révèle étrange. La multiplication étant commutative et associative, on peut définir $$$n!$ tout comme le produit de tous les entiers de $$$1$ avant $$$n$ sans se soucier de l'ordre des opérations. Mais lors de la division, l'ordre ne peut être ignoré. Dans le cas général $$$x \ mathbin {/} y \ ne y \ mathbin {/} x$ et $$$(x \ mathbin {/} y) \ mathbin {/} z \ ne x \ mathbin {/} (y \ mathbin {/} z)$ .

Dans le tweet de Farm Library, les séparateurs sont en ordre décroissant: $$$n, n-1, n-2, \ ldots, 1$ . De toute évidence, cela sera remplacé par un ordre croissant: $$$1, 2, 3, \ ldots, n$ . Que se passe-t-il si nous définissons la factorielle de division comme $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ ? Un autre retour à l'algorithme de division fractionnaire de l'école nous donne une réponse simple:

$$

$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n = \ frac {1} {2 \ times 3 \ times 4 \ times \ cdots \ times n} = \ frac {1} {n!}$$

En d'autres termes, lorsque nous divisons plusieurs fois, en comptant $$$1$ avant $$$n$ , le résultat final sera égal à la réciproque $$$n!$ . (Je voudrais mettre un point d'exclamation à la fin de cette phrase, mais hélas!) Si vous cherchez une réponse canonique à la question «Qu'obtenons-nous en divisant au lieu de multiplier en $$$n!$ ? ", Alors je dirais que $$$\ frac {1} {n!}$ Est un meilleur candidat que $$$\ frac {n} {(n - 1)!}$ . Pourquoi n'acceptons-nous pas la symétrie entre $$$n!$ et sa valeur inverse?

Bien sûr, il existe de nombreuses autres façons de placer n valeurs entières dans l'ensemble $$$\ {1 \ ldots n \}$ . Mais combien exactement? Comme il s'est avéré, exactement $$$n!$ ! Par conséquent, il peut sembler $$$n!$ façons uniques de définir une fonction de division $$$n!$ . Cependant, l'étude des réponses des deux permutations ci-dessus nous fait comprendre qu'un modèle plus simple fonctionne ici. Quel que soit l'élément de la séquence qui apparaît en premier, il apparaît au numérateur d'une grande fraction, et le produit de tous les autres éléments est le dénominateur. Par conséquent, à la fin, il n'y a que $$$n$ résultats différents (en supposant que nous effectuons toujours des opérations de division strictement de gauche à droite). Pour tout entier $$$k$ dans la gamme de $$$1$ avant $$$n$ en définissant $$$k$ au début de la ligne, nous créons une division $$$n!$ égal à $$$k$ divisé par tous les autres facteurs. Vous pouvez écrire ceci comme suit:

$$

$$\ cfrac {k} {\ frac {n!} {k}}, \ text {qui peut être converti en} \ frac {k ^ 2} {n!}$$

Et donc nous avons résolu une petite énigme sur la façon dont dans ce tweet $$$\ frac {n} {(n-1)!}$ transformé en $$$\ frac {n ^ 2} {n!}$ .
Il convient de noter que toutes ces fonctions convergent vers zéro lorsque $$$n$ à l'infini. D'un point de vue asymptotique, $$$\ frac {1 ^ 2} {n!}, \ frac {2 ^ 2} {n!}, \ ldots, \ frac {n ^ 2} {n!}$ identique.

---

Oui! Mission accomplie. Le problème est résolu. Le travail est terminé. Maintenant, nous savons tout ce dont nous avons besoin pour diviser les factoriels, non?

Eh bien, il y a peut-être encore une question. Que dira l'ordinateur? Si nous prenons notre algorithme factoriel préféré, et faisons ce qui est proposé dans un tweet, en remplaçant toutes les occurrences de l'opérateur $$$\ fois$ (ou * ) le / , que se passera-t-il? Lequel de $$$n$ options de division $$$n!$ le programme nous donnera-t-il?

Voici mon algorithme préféré pour calculer les factorielles en tant que programme sur Julia :

 function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end end 

Cet algorithme a introduit des générations entières de nerds au concept de récursivité. Sous forme de texte, il indique: si $$$n$ est égal $$$1$ alors $$$mul! (n)$ est égal $$$1$ . Sinon, vous devez calculer la fonction $$$mul! (n-1)$ puis multipliez le résultat par $$$n$ .

_{Vous pouvez demander ce qui se passe si} $$_{$n$ sera nul ou négatif. Vous pouvez demander, mais il vaut mieux ne pas le faire. Pour nos objectifs actuels} $$_{$n \ in \ mathbb {N}$ .}

Commençant par tout positif $$$n$ , la séquence d'appels récursifs tombera tôt ou tard sur $$$n = 1$ .

Une fonction peut être écrite plus succinctement en utilisant le style de définition Julia sur une seule ligne:

 mul!(n) = n == 1 ? 1 : n * mul!(n - 1) 

La partie droite de l'opérateur d'affectation est-elle une expression conditionnelle ou un opérateur ternaire de la forme a ? b : c a ? b : c . Voici a la condition booléenne du test, qui doit renvoyer true ou false . Si a est true , l'expression b évaluée et le résultat devient la valeur de l'expression entière. Sinon, c calculé.

Juste pour m'assurer que j'ai tout bien fait, voici les 10 premiers factoriels calculés par ce programme:

 [mul!(n) for n in 1:10] 10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 

Maintenant, modifions cette définition et transformons la seule occurrence * dans / , en laissant tout le reste inchangé (à l'exception du nom de la fonction).

 div!(n) = n == 1 ? 1 : n / div!(n - 1) 

Et c'est ce que le programme retournera si nous l'exécutons pour les valeurs $$$n$ de $$$1$ avant $$ :

 [div!(n) for n in 1:20] 20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418 

Quoi? Ce n'est certainement pas comme converger vers zéro, tout comme $$$\ frac {1} {n!}$ ou $$$\ frac {n} {n - 1}$ . En fait, les valeurs ne ressemblent pas à cela, car elles ne vont pas converger. A en juger par le graphique ci-dessous, la séquence se compose de deux composantes intermittentes, dont chacune semble croître lentement vers l'infini, et s'écarte également de l'autre.


Comprenant ce que nous observons ici, il sera utile de changer le type de sortie de la fonction div! . Au lieu d'utiliser l'opérateur de division / , qui renvoie la valeur sous forme de nombre à virgule flottante, nous pouvons le remplacer par l'opérateur // , qui renvoie la valeur rationnelle exacte, arrondie au terme le plus bas.

 div!(n) = n == 1 ? 1 : n // div!(n - 1) 

Voici une séquence de valeurs pour n 1:20 :

 20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189 

La liste regorge de modèles intéressants. Il s'agit d'une double hélice dans laquelle les nombres pairs et impairs en zigzags se déplacent dans des threads complémentaires. Les nombres pairs ne sont pas seulement pairs, ils sont tous des degrés $$$2$ . De plus, ils apparaissent par paires - d'abord au numérateur, puis au dénominateur - et leur séquence n'est pas décroissante. Mais il y a des lacunes; tous les diplômes ne sont pas présents $$$2$ . Le fil impair semble encore plus complexe, différents petits coefficients simples apparaissent et disparaissent dans les nombres. (Les nombres premiers doivent être petits, au moins moins $$$n$ .)

Ce résultat m'a surpris. Je m'attendais à voir une séquence beaucoup plus douce, comme celles que j'ai calculées sur papier. Tous ces sauts brisés de haut en bas n'avaient aucun sens. La tendance générale à une croissance illimitée du ratio n'avait pas non plus de sens. Comment diviser constamment, tout en recevant de plus en plus de nombres?

À ce stade, vous pouvez interrompre la lecture et essayer de trouver votre propre théorie sur l'origine de ces nombres en zigzag. Si vous avez besoin d'un indice, alors vous l'avez, et un très fort, presque un spoiler: recherchez une séquence de numérateurs ou une séquence de dénominateurs dans l'Encyclopédie en ligne des séquences entières .

---

Voici un autre indice. Un petit changement dans le programme div! convertit complètement la sortie. Modifiez simplement la dernière expression en remplaçant n // div!(n - 1) par div!(n - 1) // n .

 div!(n) = n == 1 ? 1 : div!(n - 1) // n 

Maintenant, les résultats ressemblent à ceci:

 10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800 

C'est la fonction inverse de la factorielle que nous avons déjà vue, une série de valeurs générées en allant de gauche à droite dans une séquence croissante de diviseurs $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ .

Sans surprise, la modification de la dernière expression d'une procédure modifie le résultat. Au final, on sait que la division n'est ni commutative ni associative. Mais il est difficile de comprendre pourquoi la séquence de valeurs générée par le programme d'origine donne une forme en zigzag si étrange. Quel mécanisme donne naissance à de telles puissances appariées de deux et alternant des valeurs impaires et paires?

J'ai trouvé que l'explication de ce qui se passe dans une séquence en zigzag est plus facile sur une version itérative de la procédure, plutôt que sur une version récursive. (Cette déclaration peut sembler ennuyeuse à ceux qui trouvent les définitions récursives plus simples, mais cela vient de se produire.) Voici à quoi ressemble le programme:

 function div!_iter(n) q = 1 for i in 1:n q = i // q end return q end 

Je déclare que cette procédure avec un cycle fonctionnel est identique à une fonction récursive, en ce sens que si div!(n) et div!_iter(n) renvoient un résultat pour un entier positif n , alors ce sera toujours le même. Voici ma preuve:

 [div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189 

Pour comprendre le processus qui génère ces nombres, considérez les valeurs séquentielles des variables $$$i$ et $$$q$ chaque fois que vous exécutez une boucle. À l'origine $$$i$ et $$$q$ sont égaux $$$1$ ; par conséquent, après la première passe du cycle, l'expression q = i // q donne $$$q$ valeur $$$\ frac {1} {1}$ . Alors $$$i = 2$ et $$$q = \ frac {1} {1}$ c'est-à-dire une nouvelle signification $$$q$ est égal $$$\ frac {2} {1}$ . Dans la troisième itération $$$i = 3$ et $$$q = \ frac {2} {1}$ cela nous donne $$$\ frac {i} {q} \ rightarrow \ frac {3} {2}$ . Si cela est toujours déroutant, alors imaginez $$$\ frac {i} {q}$ comment $$$i \ times \ frac {1} {q}$ . Une observation importante ici est qu'avec chaque cycle de boucle $$$q$ obtient la valeur opposée, devenant $$$\ frac {1} {q}$ .

Si vous développez ces opérations et examinez les multiplications et les divisions incluses dans chaque élément de la série, un schéma apparaît:

$$

$$\ frac {1} {1}, \ quad \ frac {2} {1}, \ quad \ frac {1 \ cdot 3} {2}, \ quad \ frac {2 \ cdot 4} {1 \ cdot 3 }, \ quad \ frac {1 \ cdot 3 \ cdot 5} {2 \ cdot 4} \ quad \ frac {2 \ cdot 4 \ cdot 6} {1 \ cdot 3 \ cdot 5}$$

Sous forme générale:

$$

$$\ frac {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n} {2 \ cdot 4 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {impair} n) \ qquad \ frac {2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n} {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot (n-1)} \ quad (\ text {even} n)$$

---

Les fonctions $$$1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n$ pour bizarre $$$n$ et $$$2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n$ pour même $$$n$ avoir leur propre nom! Ils sont appelés doubles factoriels, et sont écrits comme $$$n !!$ .

_{Terminologie horrible, non? Ce serait mieux s'ils étaient appelés «semi-factoriels». Et si je ne savais pas, je lirais} $$_{$n !!$ comme factorielle factorielle.}

Le double factoriel n est défini comme le produit de n et de tous les entiers positifs plus petits de la même parité. Donc, notre curieuse séquence de valeurs en zigzag est juste $$$\ frac {n !!} {(n-1) !!}$ .

Un article de 2012 de Henry W. Gould et Jocelyn Quentens (hélas, derrière le mur payant) explore l'utilisation des factorielles doubles. Ils sont beaucoup plus courants que vous ne le pensez. Au milieu du XVIIe siècle, John Wallis a dérivé l'identité suivante:

$$

$$\ frac {\ pi} {2} = \ frac {2 \ cdot 2 \ cdot 4 \ cdot 4 \ cdot 6 \ cdot 6 \ cdots} {1 \ cdot 3 \ cdot 3 \ cdot 5 \ cdot 5 \ cdot 7 \ cdots} = \ lim_ {n \ rightarrow \ infty} \ frac {((2n) !!) ^ 2} {(2n + 1) !! (2n - 1) !!}$$

Une série encore plus étrange impliquant un cube de valeurs factorielles doubles est résumée dans $$$\ frac {2} {\ pi}$ . Il a été découvert par nul autre que Srinivasa Ramanujan.

Gould et Kientens ont également considéré l'équivalent factoriel double pour les coefficients binomiaux. Le coefficient binomial standard est défini comme:

$$

$$\ binom {n} {k} = \ frac {n!} {k! (n-k)!}$$

La version double ressemble à ceci:

$$

$$\ left (\! \ binom {n} {k} \! \ right) = \ frac {n !!} {k !! (n-k) !!}$$

Notez que nos nombres en zigzag correspondent à cette description, et peuvent donc être considérés comme des coefficients binomiaux de factorielles doubles. Plus précisément, ce sont de tels nombres:

$$

$$\ left (\! \ binom {n} {1} \! \ right) = \ left (\! \ binom {n} {n - 1} \! \ right) = \ frac {n !!} {1 !! (n-1) !!}$$

Haricot nature $$$\ binom {n} {1}$ pas très intéressant; il est juste égal $$$n$ . Mais la version double $$$\ gauche (\! \ binom {n} {1} \! \ droite)$ comme nous l'avons vu, une danse plus vivante danse. Et contrairement au binôme habituel, il n'est pas toujours entier. (Les seules valeurs entières sont $$$1$ et $$$2$ .)

Un regard sur les nombres en zigzag en tant que quotient de factorielles doubles explique un certain nombre de leurs propriétés, à commencer par l'alternance de valeurs paires et impaires. Nous pouvons également voir pourquoi tous les nombres pairs de la séquence sont des puissances de 2. Considérons l'exemple avec $$$n = 6$ . Le numérateur de cette fraction est $$$2 \ cdot 4 \ cdot 6 = 48$ recevoir de $$ multiplicateur $$$3$ . Mais le dénominateur est $$$1 \ cdot 3 \ cdot 5 = 15$ . Les triplets au-dessus et en dessous se rétrécissent, nous laissant $$$\ frac {16} {5}$ . De telles réductions se produisent dans chaque cas. Chaque fois qu'un facteur impair apparaît dans la séquence des nombres pairs $$$m$ , il a nécessairement la forme $$$2 \ cdot m$ mais à ce moment-là même $$$m$ devrait déjà apparaître dans une séquence de nombres impairs.

---

Une séquence de nombres en zigzag est-elle une réponse raisonnable à la question: «Que se passe-t-il si nous divisons plutôt que $$$n!$ ? " Ou le programme informatique qui les génère s'est-il avéré être un algorithme erroné? À mon avis personnel, $$$\ frac {1} {n!}$ - une réponse plus intuitive, mais $$$\ frac {n !!} {(n - 1) !!}$ - plus intéressant.

De plus, l'existence même d'une séquence en zigzag élargit nos horizons. Comme indiqué ci-dessus, si vous insistez pour que l'algorithme de division passe toujours dans l'ordre dans la liste des numérateurs $$$n$ , à chaque étape en divisant le nombre à gauche par le nombre à droite, il y a un total $$$n$ résultats possibles, et ils se ressemblent tous. Mais la solution en zigzag offre des possibilités beaucoup plus larges. On peut formuler le problème comme suit: prendre l'ensemble des numérateurs $$$\ {1 \ dots n \}$ , choisissez son sous-ensemble et inversez tous les éléments de ce sous-ensemble; Maintenant, nous multiplions tous les numérateurs, à la fois inverses et directs. Si le sous-ensemble inversé est vide, le résultat sera une factorielle régulière $$$n!$ . Si tous les numérateurs sont devenus inverses à leurs valeurs, alors nous obtenons le contraire $$$\ frac {1} {n!}$ . Et si chaque deuxième numérateur est converti, en commençant par $$$n - 1$ , alors le résultat sera un élément d'une séquence en zigzag.

Ce ne sont là que quelques-unes des nombreuses options disponibles; au total il y a $$$2 ^ n$ sous-ensembles de $$$n$ éléments. Par exemple, vous pouvez prendre l'inverse de chaque nombre qui est premier ou une puissance principale $$$(2, 3, 4, 5, 7, 8, 9, 11, \ points)$ . Au petit $$$n$ les résultats sautent, mais restent constamment inférieurs à $$$1$ :


Cependant, si je continuais ce tableau pour plus $$$n$ , il décollait dans la stratosphère. Les degrés des nombres premiers deviennent très clairsemés sur la droite numérique.

---

Je vais maintenant poser une question. Nous avons vu des variations factorielles approchant zéro comme $$$n$ à l'infini par exemple $$$1 / n!$ . Nous avons vu d'autres variations croître avec l'augmentation $$$n$ illimité, y compris moi-même $$$n!$ et les nombres en zigzag. Existe-t-il des variétés du processus factoriel qui convergent vers une frontière finie qui n'est pas nulle?

Tout d'abord, l'algorithme suivant m'est venu à l'esprit:

 function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q end 

Nous parcourons des valeurs entières de $$$n$ jusqu'à $$$1$ calculer le produit / quotient actuel dans le processus $$$q$ . À chaque étape, si la valeur actuelle $$$q$ plus $$$1$ , nous le divisons par le numérateur suivant, sinon, nous effectuons la multiplication. Ce schéma met en œuvre une sorte de gestion de la rétroaction ou un comportement de recherche cible. Si $$$q$ devenant trop gros, nous le réduisons; s'il est trop petit, nous l'augmentons. J'ai suggéré que tout en s'efforçant $$$n$ à l'infini $$$q$ convergera vers une gamme de valeurs en constante diminution à côté de $$$1$ .

Mais l'expérience m'a donné une autre surprise:


Une telle vague en dents de scie n'est pas tout à fait ce à quoi je m'attendais. Curieusement, la courbe n'est pas symétrique autour $$$1$ ; les écarts par rapport au dessus ont une amplitude plus grande que par le dessous. Mais cette distorsion est plus visuelle que mathématique. Depuis $$$q$ est privé, à distance de $$$1$ avant $$ identique à la distance de $$$1$ avant $$$\ frac {1} {10}$ mais sur une échelle linéaire ne ressemble pas à ça. Vous pouvez résoudre ce problème en compilant un graphique logarithmique du quotient:


Maintenant, le graphique est symétrique, ou au moins approximativement le même, et centré par rapport à la valeur $$$0$ qui est le logarithme $$$1$ . Mais il reste un secret plus sérieux. La vague en dents de scie est très régulière et a une période $$$4$ , sans montrer de signes de compression dans le sens de la valeur limite attendue $$$\ log q = 0$ . Les valeurs numériques suggèrent que lorsque $$$n$ à l'infini, les pics de la courbe convergent vers une valeur légèrement supérieure $$$q = \ frac {5} {3}$ , et les bas approchent d'une valeur légèrement inférieure $$$q = \ frac {3} {5}$ . (Logarithmes de base correspondants $$ sont approximativement égaux $$$\ pm0.222$ ) Je n'ai pas pu comprendre pourquoi cela se produit. Peut-être que quelqu'un peut expliquer.

Un échec avec cet algorithme gourmand ne signifie pas que nous ne pouvons pas diviser la $$$q = 1$ .

_{Si nous travaillons avec les logarithmes des numérateurs, alors cette procédure devient le cas d'un problème de calcul bien connu appelé le «problème de la division d'un ensemble de nombres». On nous donne de nombreux nombres réels et nous devons les diviser en deux ensembles dont la somme est égale ou aussi proche que possible de l'égalité. Il s'agit d'une tâche qui s'est avérée difficile, mais elle est également appelée ( PDF ) «la tâche complexe la plus simple».}

Pour tout $$$n$ nous pouvons constater qu'en utilisant les valeurs inverses d'un autre sous-ensemble de numérateurs nous donne une meilleure approximation de $$$n! = 1$ . Pour les petits $$$n$ nous pouvons résoudre ce problème par la force brute: il suffit de tout considérer $$$2 ^ n$ sous-ensembles et choisissez le meilleur.

J'ai calculé les partitions optimales jusqu'à $$$n = 30$ lorsque vous devez choisir parmi un milliard d'options.


De toute évidence, le graphique devient plus plat. Vous pouvez utiliser la même méthode pour forcer la convergence vers toute autre valeur comprise entre $$$0$ avant $$$n!$ .

Et donc nous obtenons une autre réponse à la question posée par le tweet et commençons notre voyage. Que se passe-t-il si nous divisons et ne nous multiplions pas $$$n!$ ? Tout ce que nous voulons.