P12 *** Solution
Publié le 03/04/2017
Résumé

P12 *** Solution

On considère un polygone convexe inscrit dans un cercle et on note $n$ le nombre de côtés.

On trace toutes les diagonales possibles : elles forment des régions à l'intérieur du polygone.

Montrer que le nombre maximal de régions ainsi obtenues pour $n\geq 3$ côtés est

$$ C(n)=\frac{1}{24}n^4-\frac{1}{4} n^3+\frac{23}{24} n^2 - \frac{3}{4} n+1 $$


On va raisonner par récurrence en observant d'abord sur un dessin ce qui se passe lorsque l'on ajoute un sommet:

On notera dans la suite $\Delta (n+1)$ le nombre maximal de nouvelles régions obtenues lorsque l'on ajoute un sommet à un polygone à $n$ sommets.

On a :

$$\Delta (n+1) = \sum_{j=1}^n [(n-j)(j-1)+1] \; \; (*)$$

En effet, pour $j$ donné on considère une diagonale $C_{n+1;j}\;$ allant du sommet numéroté $n+1$ sur le dessin au sommet numéroté $j$.  Dans la configuration du dessin il y a donc $j-1$ sommets à droite de la corde et chacun de ces sommets est relié à $n-j$ sommets à gauche de la corde. 

On en déduit que la diagonale $C_{n+1;j} \;$ coupe $(n-j)(j-1)$ diagonales en au plus autant de points distincts (il se pourrait que l'on tombe sur un croisement de diagonales). Ainsi on forme au plus $(n-j)(j-1)+1$ nouvelles régions.

Reste à estimer  $\Delta (n+1)$, ce qui revien à calculer des sommes classiques.

$$\displaystyle  \begin{array}{rcl}\displaystyle \Delta(n+1) & = &\displaystyle \sum_{j=1}^n[(n-j)(j-1)+1] \\ & = & \displaystyle\sum_{j=1}^n jn-\sum_{j=1}^n n-\sum_{j=1}^n j^2+\sum_{j=1}^n j+\sum_{j=1}^n 1 \\ & = & \displaystyle\frac{n^2(n+1)}{2}-n^2-\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}+n \\ & = & \displaystyle\frac{n^3-3n^2+8n}{6} \end{array} $$

On peut alors démontrer la formule générale :

$$C(n+1) = C(n) + \Delta (n+1) = \displaystyle\frac{1}{24}n^4-\frac{1}{4} n^3+\frac{23}{24} n^2 - \frac{3}{4} n+1 + \frac{n^3-3n^2+8n}{6}$$

Le dernier membre s'écrit aussi :

$$\frac{n^4-2 n^3 + 11 n^2 + 14 n + 24}{24}$$ ce qui est précisément l'expression attendue (en remplaçant $n$ par $n+1$ dans la formule initiale).

 
 
 
 
 
Dernières publications