Sujet
Un pays comporte \(n\) régions. Pour des raisons d'économie, on décide de grouper ces régions deux par deux (une région, au maximum, sera laissée inchangée).
- On ne tient pas compte, dans cette question, de la situation géographique, c'est-à-dire que deux régions peuvent être regroupées même si elles sont éloignées.
a) De combien de façons peut-on effectuer ces regroupements pour \(n=2\) ? \(n=3\) ? \(n=5\) ?
b) Exprimer le nombre \(r(n)\) de regroupements possibles en fonction du nombre \(n\) de régions.
c) Quel est le nombre de regroupements pour un pays comportant 22 régions ?
Il semble plus logique de n'envisager que les regroupements entre régions voisines…dans la suite, on ne regroupera que des régions ayant une véritable frontière commune, et non celles qui n'ont qu'un sommet commun.
2. a) On suppose que la configuration est la suivante :
Quel est le nombre de regroupements possibles?
b) Même question pour le pays modélisé ci-dessous :
- Le cas général étant compliqué, on supposera que le pays peut être modélisé par une grille rectangulaire, de \(p\) lignes et \(q\) colonnes ( \(p\) et \(q\) entier non nuls), chacune des cases représentant une région. On notera alors \(r(p ; q)\) le nombre de regroupements possibles.
a) Déterminer \(r(1 ; q)\) et \(r(p ; 1)\).
b) Déterminer \(r(2 ; 2), r(2 ; 3)\) et \(r(2 ; 4)\).
c) Démontrer que pour tout entier \(q\) supérieur ou égal à 2 , \(r(2 ; q+1)=r(2 ; q)+r(2 ; q-1)\).
d) Écrire un algorithme permettant le calcul direct de \(r(2 ; q), q\) étant un entier supérieur à 2 . Donner alors la valeur de \(r(2 ; 11)\).