Olympiades · Académique Nantes · 2014 · Série S
Un ensemble \(A\) d'entiers naturels distincts est dit bi-connexe si pour tout \(x\in A\), au moins un de \(x-1\) ou \(x+1\) appartient à \(A\) (aucun élément « isolé »). Exemple : \(\{2013,2014\}\) est bi-connexe ; \(\{2,3,6,8,9\}\) ne l'est pas (\(6\) est isolé).
1. Quel entier ajouter à \(\{2,3,6,8,9\}\) pour le rendre bi-connexe ?
2. Parmi les ensembles bi-connexes contenant tous les nombres premiers \(\leq13\), lequel a le moins d'éléments ?
3. On retire au hasard un élément de \(\{1,\dots,10\}\) : probabilité que l'ensemble reste bi-connexe ?
4. Combien de sous-ensembles bi-connexes à 3 éléments dans \(\{1,\dots,2014\}\) ?
5a. Lister tous les sous-ensembles bi-connexes à 4 éléments dans \(\{1,\dots,6\}\). 5b. Combien dans \(\{1,\dots,n\}\), \(n\geq4\) ? 5c. Plus petit \(n\) tel que ce nombre dépasse \(2014\) ?
6. Soit \(u_n\) le nombre de sous-ensembles bi-connexes de \(\{1,\dots,n\}\) (\(u_2=1\), \(u_3=3\)). a) Justifier \(u_4=6\). b) Pour \(n>4\) : \(u_n=2u_{n-1}-u_{n-2}+u_{n-3}+1\). Un algorithme itère cette relation 10 fois à partir de \(u_2,u_3,u_4\) : quelle valeur affiche-t-il, et que représente-t-elle ? c) Modifier l'algorithme pour afficher le plus petit \(n_0\) tel que \(u_{n_0}\geq2014\).
4. Un sous-ensemble bi-connexe à 3 éléments doit être formé de 3 entiers consécutifs (sinon un élément serait isolé).
5b. Distinguer deux types de configurations à 4 éléments : un bloc de 4 entiers consécutifs, ou deux paires consécutives séparées par un écart. Compter chaque type séparément.
6a. Énumérer directement tous les sous-ensembles bi-connexes (de toute taille \(\geq2\)) de \(\{1,2,3,4\}\).
1. En ajoutant \(5\) ou \(7\), l'ensemble devient bi-connexe (\(6\) obtient alors un voisin).
2. Nombres premiers \(\leq13\) : \(2,3,5,7,11,13\). En ajoutant \(6\) (voisin commun de \(5\) et \(7\)) et \(12\) (voisin commun de \(11\) et \(13\)) : \(\{2,3,5,6,7,11,12,13\}\) (8 éléments), le minimum possible.
3. Retirer \(1\) ou \(10\) (les extrémités) ou tout élément intermédiaire préserve la bi-connexité (le retrait scinde en deux blocs de taille \(\geq2\)). Seuls les retraits de \(2\) ou \(9\) isolent respectivement \(1\) ou \(10\). Probabilité \(=\dfrac8{10}=\dfrac45=0{,}8\).
4. Un sous-ensemble bi-connexe à 3 éléments est nécessairement de la forme \(\{k,k+1,k+2\}\) : de \(\{1,2,3\}\) à \(\{2012,2013,2014\}\), soit \(2012\) sous-ensembles.
5a. Dans \(\{1,\dots,6\}\) : \(\{1,2,3,4\}\), \(\{1,2,4,5\}\), \(\{1,2,5,6\}\), \(\{2,3,4,5\}\), \(\{2,3,5,6\}\), \(\{3,4,5,6\}\) — 6 sous-ensembles.
5b. \(n-3\) blocs de 4 consécutifs, plus les combinaisons de deux paires disjointes non adjacentes : au total, \(\dfrac{(n-2)(n-3)}2\) sous-ensembles bi-connexes à 4 éléments.
5c. \(\dfrac{(n-2)(n-3)}2>2014\iff n^2-5n-4022>0\iff n\geq\boxed{66}\) (\(65\) donne \(1953<2014\), \(66\) donne \(2016>2014\)).
6a. Dans \(\{1,2,3,4\}\) : \(\{1,2\},\{2,3\},\{3,4\}\) (taille 2), \(\{1,2,3\},\{2,3,4\}\) (taille 3), \(\{1,2,3,4\}\) (taille 4) : \(u_4=6\).
6b. En itérant \(u_n=2u_{n-1}-u_{n-2}+u_{n-3}+1\) à partir de \(u_2=1,u_3=3,u_4=6\) : \(u_5=11\), \(u_6=20\), \(u_7=36\), \(u_8=64\), \(u_9=113\), \(u_{10}=199\), \(u_{11}=350\), \(u_{12}=615\), \(u_{13}=1080\), \(u_{14}=1896\). Après 10 itérations (calculant \(u_5\) à \(u_{14}\)), l'algorithme affiche \(1896=u_{14}\), le nombre de sous-ensembles bi-connexes de \(\{1,\dots,14\}\).
6c. En remplaçant la boucle « Pour » par une boucle « Tant que \(u<2014\) » (avec compteur), l'algorithme s'arrête dès que \(u\geq2014\) : comme \(u_{14}=1896<2014\) et \(u_{15}=2\times1896-1080+615+1=3328\geq2014\), \(n_0=15\).