🔢 mathematics

The Nim-Sum of a Random Integer Partition

Cet article détermine le comportement asymptotique du premier ordre de la proportion de positions perdantes parmi les partitions d'entiers de $N$ . La proportion tend vers zéro à l'échelle $1/(\sqrt{N}\log N)$ , mais après normalisation par son échelle naturelle, elle ne converge pas ; elle présente au contraire un motif en dents de scie dyadique avec une transition de parité de Poisson près des frontières dyadiques.

Auteurs originaux : Daewon Kim

Publié 2026-08-28✓ Author reviewed ⓘ

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Daewon Kim

Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un jeu se jouant avec des tas de pierres, où deux joueurs se relaient pour retirer n'importe quel nombre de pierres d'un seul tas. Le but est d'être le dernier à jouer, ou inversement, de forcer l'adversaire dans une position où il n'a plus de coup gagnant. C'est le jeu de Nim, un casse-tête classique de stratégie qui est étudié depuis plus d'un siècle. Le secret pour gagner ne réside pas dans le comptage du nombre total de pierres, mais dans une manière spécifique de combiner la taille des tas en utilisant une règle qui mélange l'addition et la soustraction de façon binaire. Si cette combinaison résulte en zéro, le joueur dont c'est le tour de jouer est voué à perdre, en supposant que son adversaire joue parfaitement. Depuis des décennies, les mathématiciens savent comment identifier ces positions perdantes pour n'importe quel arrangement spécifique de tas. Mais une question plus profonde, plus insaisissable, demeurait : si l'on rassemble simplement un nombre fixe de pierres et qu'on les divise en tas de manière aléatoire, quelle est la fréquence à laquelle un tel arrangement aléatoire s'avère être une position perdante ?

Cette question se situe à l'intersection de la théorie des jeux et de l'étude des partitions d'entiers, qui est le domaine mathématique concerné par la manière dont un nombre peut être décomposé en nombres entiers plus petits. Bien que les règles pour gagner un seul jeu soient précises et déterministes, le comportement de ces jeux lorsque la position de départ est choisie au hasard est étonnamment complexe. Une question naturelle est de savoir si la fréquence de ces positions perdantes se stabilise selon un modèle asymptotique simple à mesure que le nombre total de pierres augmente. Cependant, les nouveaux travaux de Daewon Kim, de l'Université de Hawaï à Mānoa, révèlent que la réponse est bien plus complexe qu'une simple stabilisation. Bien que la probabilité brute de trouver une position perdante diminue et tende vers zéro à mesure que le nombre de pierres augmente, la densité de ces positions, une fois ajustée par rapport à sa tendance naturelle, ne se stabilise jamais. Au lieu de s'aplanir en une moyenne constante, cette densité normalisée oscille selon un motif dentelé et répétitif qui ne converge jamais, peu importe l'importance du nombre de pierres.

Les recherches de Kim se concentrent sur le cas spécifique où le nombre total de pierres est pair, car les règles du jeu rendent impossible qu'un total impair forme une position perdante. En utilisant une méthode de comptage exact plutôt que de simples échantillons aléatoires, l'étude détermine précisément comment la probabilité d'une position perdante se comporte à mesure que le nombre total de pierres augmente. Les résultats montrent que cette densité normalisée n'approche pas une valeur constante unique. Au lieu de cela, elle fluctue de manière sauvage, montant et descendant selon un motif en dents de scie qui se répète chaque fois que l'échelle naturelle associée à la taille du problème franchit une puissance de deux. Si vous traciez cette densité par rapport à la taille du tas, vous verriez une ligne qui grimpe régulièrement d'un point bas vers un point haut, puis redescend brusquement, pour recommencer à grimper. Ce cycle se répète indéfiniment, ce qui signifie que la densité normalisée peut se situer n'importe où entre une et deux fois une valeur de base spécifique, selon l'endroit où vous vous trouvez dans ce cycle.

Le mécanisme qui sous-tend ce comportement est ancré dans la nature binaire de la règle de victoire du jeu. Lorsqu'un grand nombre est décomposé en parties plus petites, les plus petites parties agissent comme une source de hasard qui brouille les bits inférieurs des nombres binaires, les faisant paraître uniformes et imprévisibles. Les parties les plus grandes sont si rares qu'elles influencent rarement le résultat. Cependant, il existe une plage spécifique de tailles de parties qui agit comme un goulot d'étranglement critique. Dans cette plage, les parties sont assez grandes pour être significatives, mais pas si grandes qu'elles disparaissent. Le nombre de parties tombant dans cette plage spécifique détermine le résultat. Comme cette plage se déplace à mesure que le nombre total de pierres augmente, l'équilibre du jeu bascule d'avant en arrière. Lorsque l'échelle naturelle franchit le seuil d'une puissance de deux, l'équilibre bascule, provoquant un saut de la densité.

Pour comprendre cela, on pourrait comparer le processus à une horloge qui se réinitialise chaque fois qu'elle atteint une certaine heure, mais dont les aiguilles se déplacent à une vitesse qui change avec la taille de l'horloge elle-même. À mesure que le nombre total de pierres augmente, la plage critique des tailles de parties remonte. La parité, c'est-à-dire le fait d'avoir un nombre pair ou impair de parties dans cette plage, est le moteur clé de l'oscillation. Parce que la distribution des parties est régie par une loi qui ressemble à une distribution de Poisson, un modèle statistique souvent utilisé pour décrire des événements rares, la chance d'avoir un nombre pair de parties dans cette plage critique oscille. Cette oscillation crée le motif en dents de scie. La recherche confirme qu'à mesure que le nombre total de pierres augmente, l'ensemble de toutes les valeurs que la densité normalisée approche remplit l'intervalle entier entre une et deux fois un facteur d'échelle spécifique.

L'étude s'étend également au-delà des simples positions perdantes. Elle montre que pour tout résultat cible fixe de la somme de Nim, la densité possède le même déclin de premier ordre, et après la même normalisation, elle suit le même profil en dents de scie dyadique. Cela suggère que la structure binaire du jeu laisse une signature permanente sur la distribution aléatoire des tas, une signature qui refuse d'être lissée par la taille même des nombres impliqués.

Pour vérifier ces prédictions théoriques, l'auteur a effectué des calculs exacts pour chaque arrangement possible de pierres jusqu'à un total de vingt mille. Cela a nécessité une approche computationnelle sophistiquée traitant le problème comme un exercice de comptage massif, utilisant des algorithmes spécialisés pour gérer les milliards de combinaisons possibles sans avoir à énumérer chaque partition individuellement. Les résultats de ces calculs ont correspondu aux prédictions théoriques avec une précision remarquable, confirmant que le motif en dents de scie est réel et non un artefact du modèle mathématique. Les données ont montré que la densité monte et descend exactement comme la théorie le prédisait, avec les transitions brusques se produisant précisément aux moments où l'échelle naturelle franchit une puissance de deux.

La recherche examine également la nature de la transition entre ces pics et ces creux. Bien que le graphique semble présenter des sauts discontinus et brusques, l'analyse des tailles finies indique que ce saut n'est pas véritablement instantané car il est en réalité lissé au sein d'une fenêtre de plus en plus étroite, un changement progressif dicté par le fait que le nombre de parties dans la plage critique est pair ou impair. À mesure que le nombre total de pierres augmente, la fenêtre dans laquelle ce lissage se produit devient plus étroite, rendant les sauts de plus en plus nets à l'œil nu, même s'ils restent mathématiquement continus. Ce phénomène explique pourquoi le motif semble si dentelé dans les données, alors que la mathématique sous-jacente est lisse.

En fin de compte, ce travail fournit une description complète de la distribution des positions perdantes dans le jeu de Nim lorsque la configuration de départ est choisie au hasard. Il résout une question de longue date sur la fréquence de ces positions, montrant qu'elles ne suivent pas une tendance simple et constante. Au lieu de cela, elles sont gouvernées par une interaction complexe entre la taille des tas et la structure binaire du jeu. Les conclusions mettent en lumière un principe plus large en mathématiques : même dans des systèmes qui semblent aléatoires et lisses, des structures arithmétiques profondes peuvent créer des motifs nets et persistants qui résistent à la moyenne. La nature binaire du jeu garantit qu'un bloc spécifique d'informations reste visible et influent, peu importe la taille du système, créant un rythme qui se répète éternellement à mesure que les nombres grandissent.

Résumé Technique : La Somme de Nim d'une Partition d'Entier Aléatoire

Énoncé du Problème
L'article étudie les propriétés énumératives des positions de Nim ordinaires avec un nombre total de jetons fixé, $N$ . Dans le Nim, une position est définie par un multiensemble de tailles de tas. D'après le théorème de Bouton, une position est perdante si et seulement si le OU exclusif (XOR) binaire des tailles de tas est nul. Lorsque l'ordre des tas est ignoré, ces positions correspondent aux partitions d'entiers de $N$ .

Le problème central est de déterminer le comportement asymptotique du rapport $a_N / p(N)$ , où $p(N)$ est le nombre total de partitions d'entiers de $N$ , et $a_N$ est le nombre de telles partitions dont la somme XOR est nulle. Bien que la restriction de parité soit immédiate ( $a_N = 0$ pour $N$ impair car la somme et le XOR partagent le même bit de poids faible), la distribution des positions perdantes pour $N$ pair présente un comportement complexe : pour $N$ pair, la densité brute tend vers zéro, tandis que la densité appropriément normalisée présente un comportement oscillatoire non convergent que les asymptotiques standards des partitions ne parviennent pas à capturer.

Méthodologie
L'auteur emploie une approche multidimensionnelle combinant décomposition combinatoire, modélisation probabiliste et théorie analytique des nombres :

Décomposition Combinatoire : L'article décompose une partition $\lambda$ en deux composantes basées sur les multiplicités de ses parties. Si une partie $j$ apparaît $c_j$ fois, elle est écrite sous la forme $c_j = 2r_j + \varepsilon_j$ où $\varepsilon_j \in \{0, 1\}$ . Les copies paires ( $2r_j$ ) s'annulent dans la somme XOR, ne laissant que le « cœur impair » (les parties avec $\varepsilon_j=1$ ). Cela réduit le problème à l'analyse du XOR d'une partition en parties distinctes.
Échantillonnage de Boltzmann : Pour exploiter l'indépendance, l'étude se déplace vers le modèle de Boltzmann où la taille totale est aléatoire. Dans ce modèle, les indicateurs pour l'inclusion de parties distinctes sont des variables de Bernoulli indépendantes. La probabilité d'une somme XOR nulle est analysée en partitionnant les entiers en trois plages dyadiques par rapport à une échelle critique $J$ $J$ :
- Bloc Inférieur ( $[1, J)$ ) : Ces petites parties randomisent les bits binaires inférieurs, créant une distribution presque uniforme sur les bits de poids faible.
- Bloc Critique ( $[J, 2J)$ ) : Cette plage détermine la probabilité de premier ordre. Chaque entier dans $[J, 2J)$ possède le même bit de poids $J$ ; ce bit de poids $J$ du XOR du bloc est nul si et seulement si le nombre de parties sélectionnées dans cette plage est pair. Conditionnellement à cela, le bloc inférieur doit correspondre au résidu des bits de poids inférieurs.
- Bloc Supérieur ( $[2J, \infty)$ ) : Ces grandes parties sont rares et contribuent de manière négligeable au terme de premier ordre.
Hiérarchie Dyadique et Analyse de Walsh : L'auteur utilise l'analyse de Walsh (orthogonalité des caractères sur $\mathbb{F}_2$ ) pour dériver des formules finies exactes et pour affiner l'approximation. La hiérarchie dyadique permet d'affiner l'approximation de Boltzmann à un ordre algébrique arbitraire, tandis que le transfert vers les partitions de taille fixée est établi uniquement au premier ordre.
Analyse de Point Selle : Pour transférer les résultats du modèle de Boltzmann (taille aléatoire) vers les partitions de taille fixée, l'article utilise des méthodes de point selle sur les fonctions génératrices. Il identifie deux points selles égaux (proches de $q = e^{-t_N}$ et $q = -e^{-t_N}$ ) en raison de la parité de la fonction génératrice pour les positions perdantes.
Calcul Exact : Un algorithme exact basé sur la formule de Walsh et le théorème des restes chinois (TRC) est implémenté pour calculer $a_N$ jusqu'à $N=20\,000$ . Cela sert à vérifier les formules asymptotiques et à analyser les corrections de taille finie.

Résultats Clés
L'article établit le comportement asymptotique de premier ordre de la densité des positions perdantes. Soient $\tau_N = \pi/\sqrt{6N}$ et $B_N = \log(1/\tau_N)/\tau_N$ . Soit $J_N$ la puissance de deux la plus proche de $B_N$ en distance multiplicative, et définissons $\Lambda_N = e^{-\tau_N J_N}/\tau_N$ .

Pour $N$ pair, le rapport est donné par :
$\frac{a_N}{p(N)} = \frac{1 + e^{-2\Lambda_N} + o(1)}{J_N}$

Les conclusions principales incluent :

Non-Convergence : La densité normalisée $B_N \frac{a_N}{p(N)}$ ne converge pas, et son ensemble de limites de sous-suites est l'intervalle complet $[1, 2]$ .
Dents de Scie Dyadiques : Le comportement suit un motif de « dent de scie dyadique ». À mesure que $N$ augmente, la valeur monte de 1 à 2 durant chaque phase binaire (lorsque $B_N$ traverse des puissances de deux) et redescend à 1 lorsque l'échelle traverse une nouvelle puissance de deux.
Lissage de Poisson : La discontinuité apparente aux frontières dyadiques est lissée sur une échelle décroissante par la loi de parité d'une variable aléatoire de Poisson. Plus précisément, si $N$ approche une frontière telle que $\tau_N K - \log(1/\tau_N) \to c$ (où $K$ est une puissance de deux), la limite est $1 + e^{-2e^{-c}}$ .
Sommes de Nim Générales : Le résultat n'est pas unique à la somme XOR nulle. Pour toute cible de somme de Nim $x$ fixée, la densité des partitions avec une somme de Nim $x$ suit le même profil de premier ordre le long de la classe de parité $N \equiv x \pmod 2$ .
Comptages Exacts : L'article étend la séquence OEIS A048833 jusqu'à l'indice 10 000 (taille totale $N=20\,000$ ), fournissant des données exactes qui confirment l'échelle prédite et la structure des erreurs de taille finie.

Signification et Revendications
L'article prétend fournir la description asymptotique complète de premier ordre des positions de Nim perdantes pour les partitions d'entiers non restreintes. Sa signification réside dans le fait qu'il révèle qu'une structure aléatoire « lisse » (partitions d'entiers) conserve une caractéristique arithmétique nette (parité binaire) en raison de l'existence d'un unique bloc dyadique critique qui reste visible après que les bits inférieurs ont été randomisés et que les bits supérieurs sont devenus négligeables.

Le travail démontre que la densité des positions perdantes est de l'ordre de $\Theta(1/(\sqrt{N} \log N))$ mais qu'elle ne possède pas de constante asymptotique unique. L'auteur souligne que la « hiérarchie dyadique » permet des raffinements à un ordre algébrique arbitraire, expliquant pourquoi les corrections de taille finie sont significatives même lorsque le théorème de premier ordre est valide. L'article conclut que la non-convergence est un trait structurel du problème, et non un échec de l'approximation, et que la transition entre les phases est gouvernée par la parité d'une variable de Poisson.

L'article ne prétend pas résoudre le problème général des sommes de Nim cibles croissantes ou des partitions restreintes, les notant comme des questions ouvertes naturelles. Il s'abstient également de prétendre que l'analyse de la correction de taille finie constitue un théorème complet de second ordre, car elle repose sur des expansions formelles plutôt que sur des bornes uniformes pour les dérivées d'ordre supérieur.

Articles similaires