Récrémaths

Un jeu de construction où chaque nombre ajouté doit soigneusement éviter son double : jusqu'où peut-on aller ?
Dans l'ensemble AA des entiers naturels que l'on veut construire, on ne doit jamais voir un nombre et son double. Comment faire en sorte que AA contienne le plus possible d'éléments ?
Première remarque : 0 ne peut pas appartenir à AA, puisqu'il est son propre double. Ensuite, si le nombre 1 appartient à AA, le nombre 2 ne peut pas être aussi élément de AA.
Une première idée sans risque est de mettre dans AA tous les nombres impairs : par définition aucun n'est le double d'un autre, donc on est tranquille, tout en ayant ainsi mis une infinité d'éléments dans AA. Pas mal pour un début, mais comment ajouter au mieux d'autres nombres à AA ?
Commençons par exemple par ajouter 4, ce qui est possible puisque AA ne contient pas 2. Ensuite, on ne peut pas ajouter 6 (qui est le double de 3), ni 8 (puisqu'on vient d'ajouter 4), ni 10 (le double de 5)… mais on peut ajouter 12 (puisque 6 n'est pas dans AA). Ensuite, on ne peut pas ajouter 14 (le double de 7), mais on peut ajouter 16 (puisqu'on n'a pas pris 8). Cette manière de faire est un peu rustique, mais vous pouvez essayer de la perfectionner.
**1. Démontrer que l'on peut ajouter une infinité de nombres pairs dans AA en respectant la contrainte.**
Le mathématicien Edward T. H. Wang s'est intéressé au nombre maximal f(n)f(n) d'éléments sans double dans un ensemble d'entiers compris entre 1 et nn. Les valeurs de cette fonction sont données par la formule de récurrence f(n)=⌈n2⌉+f(⌊n4⌋)f(n) = \left\lceil \dfrac{n}{2} \right\rceil + f\left( \left\lfloor \dfrac{n}{4} \right\rfloor \right), avec f(1)=1f(1) = 1.
Dans cette formule, l'expression ⌈n2⌉\left\lceil \dfrac{n}{2} \right\rceil correspond au plus petit entier supérieur ou égal à n/2n/2, et ⌊n4⌋\left\lfloor \dfrac{n}{4} \right\rfloor au plus grand entier inférieur ou égal à n/4n/4.
2. Combien d'entiers naturels peut-on prendre au maximum entre 1 et 2026 de telle sorte qu'aucun ne soit le double d'un autre ?

Interdit de tripler

On peut également s'intéresser aux ensembles sans triples, ne contenant jamais un nombre et son triple, sans quadruples, sans quintuples, etc. Pour cela, une généralisation de la formule de Wang a été trouvée par J. Y.-T. Leung et W.-D. Wei pour le nombre maximal f(n)f(n) d'éléments des sous-ensembles sans kk-uples de l'ensemble des entiers de 1 à nn :
f(1)=1,f(n)=n−⌊nk⌋+f(⌊nk2⌋).f(1) = 1, \quad f(n) = n - \left\lfloor \frac{n}{k} \right\rfloor + f\left( \left\lfloor \frac{n}{k^2} \right\rfloor \right).
On peut vérifier que cette formule coïncide bien avec la précédente lorsque kk est égal à 2.
3. Quel est le nombre maximal d'éléments d'un sous-ensemble ne contenant le triple d'aucun de ses éléments et inclus dans l'ensemble des entiers naturels de 1 à 100 ? 4. Donner un exemple d'un tel sous-ensemble.

Références

  • *On double-free sets of integers*, Edward T. H. Wang, *Ars Combinatoria* 28, 1989.
  • *Maximal k-Multiple-Free Sets of Integers*, Joseph Y.-T. Leung et W.-D. Wei, *Ars Combinatoria* 38, 1994.
641dead7a349b7ce6f58a76930678a51b5e38b720e94b7f60ce05431d1aeae42.jpg