🔢 mathematics

Partitioning set $[n] = \{1, \dots, n\}$ into subsets of size at most $m$ such that all sums are powers of $m$

Cet article étudie l'existence et l'unicité de partitions de l'ensemble $\{1, \dots, n\}$ en sous-ensembles de taille au plus $m$ dont les sommes sont des puissances de $m$ , démontrant que si de telles partitions échouent pour une infinité de $n$ lorsque $m > 3$ , elles existent probablement pour tout $n$ lorsque $m = 3$ (sous réserve de contraintes spécifiques sur les contre-exemples potentiels) et établissant des décomptes exacts du nombre de telles partitions pour diverses valeurs de $n$ .

Auteurs originaux : Vladimir Gurvich, Mariya Naumova

Publié 2026-07-17

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Vladimir Gurvich, Mariya Naumova

Article original sous licence CC BY 4.0 (http://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 ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un maître architecte chargé de construire une ville en utilisant exactement $n$ briques uniques, numérotées de 1 à $n$ . Votre objectif n'est pas seulement de les empiler ; vous devez les regrouper en quartiers (appelés « parties ») où deux règles strictes s'appliquent. Premièrement, aucun quartier ne peut être trop encombré ; il peut contenir au plus $m$ briques. Deuxièmement, le « poids » total des briques de chaque quartier doit être une puissance parfaite d'un nombre magique spécifique $m$ (comme $m^0=1$ , $m^1=m$ , $m^2$ , et ainsi de suite). Ce casse-tête appartient au monde de la combinatoire, une branche des mathématiques qui étudie la façon dont les choses peuvent être disposées, comptées ou regroupées. C'est comme résoudre un Sudoku géant et infini où les règles changent en fonction de la taille de la grille. Les mathématiciens se soucient de cela car comprendre comment les nombres peuvent être décomposés et réassemblés révèle les secrets profonds de la structure des mathématiques, tout comme la compréhension de la façon dont les atomes se lient aide à construire de nouveaux matériaux.

L'article que vous allez lire traite d'une version spécifique et complexe de ce casse-tête, où les auteurs, Vladimir Gurvich et Mariya Naumova, fixent le nombre magique $m$ à 3. Cela signifie qu'ils essaient de diviser les nombres de 1 à $n$ en groupes de taille 1, 2 ou 3, où la somme de chaque groupe est une puissance de 3 (1, 3, 9, 27, etc.). Ils savaient déjà que pour $m=2$ , il existe toujours exactement une façon de le faire pour n'importe quel $n$ . Ils savaient aussi que pour un $m$ supérieur à 3, le casse-tête est impossible pour une infinité de valeurs de $n$ . Mais pour $m=3$ , la réponse était un mystère. Les auteurs supposent fortement (conjecturent) qu'une solution existe pour chaque nombre $n$ , peu importe sa taille.

Pour tester cela, ils ne se sont pas contentés de deviner ; ils ont construit un filet de sécurité mathématique. Ils ont prouvé que si une solution n'existe pas pour un certain nombre $n$ , ce « mauvais » nombre doit avoir une forme très spécifique et étrange. Il doit ressembler à $n = 3t + 3k + 2$ , et il doit éviter certains autres schémas spécifiques. Imaginez un détective disant : « Si un crime a eu lieu, le suspect doit porter un chapeau rouge, boiter et être gaucher. » Si vous trouvez un suspect qui ne correspond pas à cette description, vous savez qu'il n'est pas le coupable. Les auteurs ont utilisé cette logique pour éliminer d'énormes pans de nombres. Ils ont également exécuté des simulations informatiques pour vérifier chaque nombre jusqu'à 844, et dans chaque cas, une solution a été trouvée. Ils ont même exploré une version légèrement plus souple du casse-tête appelée « quasi-partition », où un nombre est autorisé à être utilisé deux fois, et ont prouvé que des solutions existent également là aussi. Bien qu'ils n'aient pas encore prouvé que le casse-tête est soluble pour chaque $n$ , ils ont réduit la recherche d'un contre-exemple à une liste très petite et spécifique de nombres, et ils sont convaincus que pour presque tous les autres nombres, la solution est non seulement possible mais souvent unique.

Le Grand Jeu du Groupement de Nombres

Imaginez que vous avez un sac de tuiles numérotées, de 1 jusqu'à un grand nombre $n$ . Votre tâche est de trier ces tuiles en piles. Mais il y a des règles !

La Règle de Taille : Chaque pile peut contenir au plus 3 tuiles.
La Règle de Somme : Les nombres de chaque pile doivent s'additionner pour donner une « puissance de 3 ». Cela signifie que la somme doit être 1, 3, 9, 27, 81, et ainsi de suite.

C'est le problème de la « partition 3-bonne ». Les auteurs posent une question simple mais tenace : Pouvons-nous toujours le faire, peu importe le nombre de tuiles avec lesquelles nous commençons ?

Pendant longtemps, les mathématiciens connaissaient la réponse pour les partitions « 2-bonnes » (où les piles ont au plus 2 tuiles et les sommes sont des puissances de 2). Il s'avère qu'il y a toujours exactement une façon de le faire. Mais pour 3, les règles deviennent compliquées. Les auteurs soupçonnent que la réponse est « Oui, c'est toujours possible », mais ils avaient besoin de le prouver.

Les Suspects « Critiques »

Au lieu d'essayer de prouver que cela fonctionne pour chaque nombre (ce qui est difficile), les auteurs ont décidé de chercher les « méchants » — les nombres où cela échoue. Ils ont raisonné que si un nombre $n$ existe où vous ne pouvez pas faire les piles, il doit être un nombre « critique ».

Ils ont prouvé que si un tel nombre critique existe, il ne peut pas être n'importe quel nombre aléatoire. Il doit porter un déguisement très spécifique. Il doit être de la forme :
$n = 3t + 3k + 2$
Et il doit satisfaire des conditions supplémentaires concernant la taille de $k$ par rapport à $t$ .

Pensez à un videur de boîte de nuit. Le videur dit : « Si vous essayez de vous faufiler sans ticket, vous devez porter un chapeau vert et porter un sac bleu. » Si vous voyez quelqu'un avec un chapeau rouge, vous savez avec certitude qu'il n'est pas l'intrus furtif. Les auteurs ont prouvé que tout nombre qui ne correspond pas à cette description du « chapeau vert » est sûr ; nous savons comment grouper ces nombres. Cela élimine une quantité massive de possibilités.

La Vérification Informatique

Même avec leur mathématiques astucieuses, il restait encore des nombres qui correspondaient à la description du « chapeau vert ». Pour être sûrs, les auteurs (avec l'aide d'un programmeur informatique nommé Dmitry Rybin) ont écrit un programme pour vérifier chaque nombre jusqu'à 844.

Le Résultat : Pour chaque nombre de 1 à 844, ils ont trouvé un moyen de grouper les tuiles parfaitement.
La Conclusion : L'ordinateur n'a trouvé aucun « mauvais » nombre. Cela soutient fortement leur hypothèse que le casse-tête est soluble pour tout le monde.

Le Tour de Passe-passe des « Quasi-Partitions »

Les auteurs ont également essayé un jeu légèrement différent. Et si nous autorisions un nombre à être utilisé deux fois ? Ils appellent cela une « quasi-partition ». Imaginez que vous avez une tuile de rechange du nombre 3, de sorte que vous puissiez l'utiliser dans deux piles différentes.

Ils ont prouvé que pour une plage spécifique de nombres, vous pouvez toujours résoudre cette version du puzzle, et le nombre 3 (spécifiquement $3^t$ ) est celui qui est utilisé deux fois. C'était une étape utile pour comprendre le problème plus difficile.

Combien y a-t-il de Façons ?

L'une des parties les plus amusantes de l'article est de compter le nombre de façons différentes de grouper les nombres.

Pour certains nombres (comme 1, 2, 3, 4 et beaucoup d'autres), il y a exactement une façon de le faire. C'est comme une serrure avec une seule clé.
Pour le nombre 13, et pour des nombres comme $3t - 3$ , il y a exactement deux façons.
Pour presque tous les autres nombres, ils soupçonnent qu'il y en a plus de deux.

Ils ont même trouvé une règle spéciale (Proposition 2) qui dit que si vous connaissez les groupes de trois nombres (triplets) qui composent la solution, vous pouvez déduire tout le puzzle. C'est comme dire : « Si vous savez qui sont les trois meilleurs amis dans une pièce, vous connaissez toute la dynamique sociale. »

L'Essentiel

Les auteurs n'ont pas encore résolu le puzzle pour chaque nombre de l'univers. Il reste encore quelques nombres délicats (comme 35, 38, 89 et 101) qui n'ont pas été totalement dégagés par leurs mathématiques. Cependant, ils ont montré que si une solution n'existe pas, elle doit être l'un de ces nombres très spécifiques et rares.

Ils sont convaincus que la « partition 3-bonne » existe pour chaque nombre $n$ . Ils ont éliminé les échecs faciles, vérifié les 844 premiers nombres avec un ordinateur, et ont constaté que le casse-tête possède toujours une solution. La question n'est pas de savoir si nous pouvons grouper les nombres, mais plutôt combien de façons nous pouvons le faire pour les très grands nombres. Le voyage pour prouver cela pour chaque nombre continue, mais le chemin est désormais bien plus clair.

Résumé Technique : Sur le partitionnement de l'ensemble [n] en sous-ensembles de taille au plus m tels que toutes les sommes soient des puissances de m

Énoncé du Problème
Le document traite d'un problème de partitionnement combinatoire défini sur l'ensemble des $n$ premiers entiers naturels, $[n] = \{1, \dots, n\}$ . Pour des entiers $m > 1$ et $n > 0$ , un sous-ensemble de $[n]$ est défini comme étant $m$ -bon si son cardinal est au plus $m$ et que la somme de ses éléments est une puissance de $m$ (c'est-à-dire $m^t$ pour un entier $t \ge 0$ ). Une partition de $[n]$ est dite $m$ -bonne si chaque partie de la partition est un ensemble $m$ -bon.

Les auteurs étudient l'existence et l'unicité de telles partitions. Il est établi que :

Pour $m=2$ , une partition 2-bonne unique existe pour tout $n$ .
Pour $m > 3$ , il existe une infinité de $n$ pour lesquels aucune partition $m$ -bonne n'existe (spécifiquement, pour $n = 2(m^t + 1)$ ).
Le cas $m=3$ est l'objet principal de l'étude, où l'existence d'une partition 3-bonne pour tout $n$ n'est pas immédiatement évidente et reste un sujet de conjecture.

Méthodologie
Les auteurs emploient une combinaison de preuves constructives, de réductions récursives et de vérifications computationnelles.

Techniques de Réduction : Le cœur de la méthodologie repose sur des « réductions », où une partition de $[n]$ est construite en ajoutant des parties spécifiques à une partition connue d'un ensemble plus petit $[n']$ . Les auteurs définissent des formules de réduction spécifiques pour diverses formes de $n$ (par exemple, $n = 3t + 3k$ , $n = 3t + 3k + 1$ ) qui permettent la construction d'une partition 3-bonne pour $n$ à partir d'une partition pour un $n'$ plus petit.
Intervalles Symétriques : Le document utilise des partitions d'intervalles d'entiers symétriques $[-\ell; \ell]$ pour faciliter les réductions. Le Lemme 1 démontre que de tels intervalles admettent des partitions 3-bonnes (en utilisant des triplets dont la somme est 0) lorsque $\ell \equiv 0, 1 \pmod 3$ .
Quasi-Partitions : Pour traiter les cas où les partitions standards sont difficiles à construire, les auteurs introduisent des quasi-partitions 3-bonnes. Il s'agit de familles de sous-ensembles qui couvrent tous les nombres de $[n]$ exactement une fois, à l'exception d'un nombre spécifique (précisément $3^t$ ) qui est couvert deux fois.
Algorithmes Récursifs : Pour les preuves d'unicité, les auteurs utilisent un algorithme récursif (attribué à Oleg Polubasoff) qui détermine le placement du plus grand nombre libre $i$ . Si $i$ est une puissance de 3, il doit être un singleton ; sinon, il doit être associé à $3^j - i$ (où $3^{j-1} < i < 3^j$ ).

Contributions Clés et Résultats

Conjecture d'Existence (Conjecture 1) : Les auteurs conjecturent qu'une partition 3-bonne de $[n]$ existe pour tout entier positif $n$ .
Caractérisation des Contre-exemples Minimaux (Théorème 1) : En supposant qu'un contre-exemple existe, les auteurs prouvent que le contre-exemple minimal $n$ $n$ doit satisfaire des conditions strictes :
- $n = 3^t + 3k + 2$ pour $t > 0$ .
- $0 \le k < \frac{3^{t-1}-1}{2}$ .
- $k \neq \frac{3^\ell-1}{2}$ pour tout entier non négatif $\ell < t$ .
- Équivalemment, $n \equiv 2 \pmod 3$ , $3k+2 < \frac{3^{t+1}+1}{2}$ , et $3k+2 \neq \frac{3^{\ell+1}+1}{2}$ .
- Cela réduit considérablement l'espace de recherche des potentiels contre-exemples.
Existence de Quasi-Partitions (Théorème 2) : Les auteurs prouvent que pour tout $n$ satisfaisant les conditions du Théorème 1 (c'est-à-dire la forme potentielle d'un contre-exemple), une quasi-partition 3-bonne existe où le nombre $3^t$ est couvert deux fois. Cela suggère que l'obstacle à une partition standard est minimal.
Résultats d'Unicité (Théorème 3) : Le document établit l'unicité des partitions 3-bonnes pour des plages spécifiques de $n$ $n$ :
- Des partitions uniques existent pour $n \in \{1, 2, 3, 4\}$ et pour $n$ de la forme $3^t - 4, 3^t - 2, 3^t - 1, 3^t, 3^t + 1, 3^t + 2, 3^t + 3, 3^t + 5$ (pour $t \ge 2$ ).
- Exactement deux partitions 3-bonnes existent pour $n = 3^t - 3$ et pour $n = 13$ .
- Les auteurs conjecturent que pour tous les autres $n$ (en excluant 13), le nombre de partitions 3-bonnes est supérieur à 2.
Vérification Computationnelle : En utilisant un code écrit par Dmitry Rybin, les conjectures concernant l'existence et le décompte des partitions ont été vérifiées pour tout $n \le 844$ .

Signification et Revendications
Le document affirme fournir les premiers résultats partiels rigoureux concernant l'existence de partitions 3-bonnes pour tout $n$ . En caractérisant la forme de tout contre-exemple minimal potentiel, les auteurs contraignent de manière significative l'espace du problème. L'introduction des quasi-partitions sert d'étape intermédiaire cruciale, démontant que même dans les cas les plus difficiles (où une partition standard pourrait échouer), une structure très proche d'une solution existe.

Les auteurs reconnaissent que bien que les méthodes de réduction généralisées (suggérées par Oleg Polubasoff) étendent la portée des cas prouvables, il reste une question ouverte de savoir si ces méthodes sont suffisantes pour prouver pleinement la Conjecture 1 pour tout $n$ . Le document ne prétend pas avoir résolu le problème général de l'existence, mais fournit un cadre structurel et des preuves solides soutenant la conjecture.