Sous-ensembles de ${\mathbb N}$

yan2 · October 2017

Bonjour,

j'avais lu, il y a 2 ou 3 ans, un exercice de combinatoire dans la revue Math. Magazine publiée par la MAA (je ne me rappelle plus exactement du numéro). Je n'ai plus accès à cette revue, et je suis curieux de voir une solution de ce problème, merci par avance pour votre aide.

Déterminer tous les sous-ensembles $H_1,H_2,\cdots \subset {\mathbb N}$ tels que :
(i) $\vert H_n\vert=n$ pour tout $n\in {\mathbb N}^*$; ($\vert S\vert$ désigne le cardinal de $S$);
(ii) $H_n\cap H_m=H_{pgcd(n,m)}$ pour tout $n,m\in {\mathbb N}^*$.

Cordialement,
Yan2

jacquot · October 2017

Bonjour,
Modulo une injection, on peut toujours commencer comme ça:
$H_1=\{0\}$
$H_2=\{0;1\}$
$H_3=\{0;2;3\}$
$H_4=\{0;1;4;5\}$
$H_5=\{0;6;7;8;9\}$
$H_6=\{0;1;2;3;10;11\}$
$H_7=\{0;12;13;14;15;16;17\}$
$H_8=\{0;1;4;5;18;19;20;21\}$
$H_9=\{0;2;3;22;23;24;25;26;27\}$
$H_{10}=\{0;1,6;7;8;9;28;29;30;31\}$ etc.

Mais il serait préférable de trouver un cryptage plus lisible...

marco · October 2017

Si on définit pour tout $n>0$, $G_n=\{\frac{k}{n}\mid k\in \N^*,\ k\leq n\}$, alors $G_n\cap G_m=G_{pgcd(n,m)}$.
$\cup_{n>0} G_n=\Q\, \cap\, ]0,1]$. Donc si on a une injection $\phi$ de $\Q\; \cap\, ]0,1]$ dans $\N$, on trouve un exemple de famille $H_1, H_2,\dots$ en posant $H_n=\phi(G_n)$.

Mais pour trouver toutes les familles...

marco · October 2017

Pour montrer l'unicité (à injection près de $\cup_{n>0} H_n$ dans $\N$), on raisonne comme Jacquot, je pense. Soit $(H'_n)$ une première famille solution, et $(H''_n)$ une deuxième famille solution.
On raisonne par récurrence.
On suppose que, par une injection de $\cup_{0<n\leq k} H'_n$ dans $\N$, on s'est ramené à une famille $(H_n)$ telle que $\cup_{0<n\leq k} H_n$ est un intervalle de $\N$ contenant $0$ (c'est-à-dire de la forme $[0,a_k]$) pour tout $k<p$.
Alors $H_p \cap (\cup_{0<n\leq p-1} H_n)= H_p \cap [0,a_{p-1}]$ est déterminé de manière unique par la propriété $H_p \cap H_n=H_{pgcd(p,n)}$.
Quant aux éléments (en nombre $b$) de $H_p-(\cup_{0<n\leq p-1} H_n)$, on les envoie sur $a_{p-1}+1,a_{p-1}+2,\dots,a_{p-1}+b$ de sorte que $\cup_{0<n\leq p} H_n$ est encore un intervalle $[0,a_p]=[0,a_{p-1}+b]$ de $\N$.
Donc l'hypothèse de récurrence est vérifiée pour tout $k<p+1$.

Sous-ensembles de ${\mathbb N}$

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 47