Démarrage trompeur

Quel est le terme suivant de la suite 2,4,8,16 ? Vous croyez savoir ? Pas si vite …

Dessinons un cercle et prenons deux points dessus, puis traçons la corde qui les relie :

En combien de régions cette corde divise-t-elle le cercle ?

En 2 régions, évidemment.

Prenons maintenant 3 points sur un cercle, et traçons toutes les cordes qui les joignent :

En combien de régions le cercle se trouve-t-il subdivisé par ces cordes ?

Ce n’est pas bien dur de les compter : il y en a 4.

Prenons ensuite 4 points… Cette fois on obtient 8 régions :

Et si on prenait 5 points ? On a une suite qui démarre par 2,4,8, il y a fort à parier que le terme suivant est 16. Faisons le dessin, pour en avoir le cœur net :

Eh oui, il y en a bien 16… Bon, alors, si on a n points sur le cercle et qu’on les relie de toutes les manières possibles, on donnera probablement naissance à 2n−1 régions, et cela doit sûrement se prouver par récurrence, sans trop de difficulté…

En tout cas, c’est la réaction qu’ont eue les collègues mathématiciens à qui j’ai montré la suite de figures précédente. Ils n’étaient pas bien intéressés…

Attendez, leur répondis-je, et comptez les régions lorsqu’on prend 6 points sur le cercle :

Ah, ce n’est plus si facile… il faut se concentrer un peu pour trouver une stratégie… il faut être sûrs de compter chaque région… mais rien qu’une seule fois… je me suis trompé, j’obtiens 31 régions… attends, je recommence… encore 31… 31 ? Il n’y en aurait pas 32 ?

Eh non, il y en a bien seulement 31. Remarquons en passant qu’il faut placer les points de telle sorte que l’on n’ait jamais trois cordes qui passent par le même point intérieur au cercle, sinon, on aurait encore moins de régions :

Notre suite démarre donc ainsi :
2,4,8,16,31.

Devinez-vous à présent le terme suivant ? Ce n’est plus du tout facile, je vous l’accorde…

« Le livre des nombres »

Avant de vous indiquer la réponse, je voudrais vous dévoiler ma source pour ce problème. Il s’agit de l’ouvrage « Le livre des nombres » de John H. Conway et Richard K. Guy ⁵Ce livre est paru en 1998 chez Eyrolles, version française de « The book of numbers », publié en 1996 par Copernicus, une marque de Springer-Verlag New York. :

J’ai pris beaucoup de plaisir à lire ce livre, qui n’est pas un recueil de problèmes, mais un récit qui promène le lecteur dans le monde des nombres, des entiers naturels aux nombres surréels introduits par Conway, l’un des auteurs ⁶Les nombres surréels ont été présentés sur ce site dans un article de Lisa Rougetet.. Bien des propriétés insolites de nombres et de suites de nombres plus ou moins célèbres y sont présentées. Ces propriétés sont démontrées lorsque ce n’est pas trop compliqué. Le rythme est alerte, parfois haletant. Une fois le livre ouvert, je n’ai pas pu m’arrêter avant de l’achever. Je le recommanderais à toute personne qui apprécie les récits mathématiques, et à tout enseignant du secondaire qui est à la recherche d’idées pour animer des clubs de maths.

 

Une preuve d’irrationnalité

Peut-on y trouver des histoires accessibles aux collégiens? Oui, certaines. Voici par exemple comment Conway et Guy expliquent l’irrationnalité de \(\sqrt{n}\), pour chaque entier naturel \(n\) qui n’est pas un carré parfait:

Supposons par l’absurde que \(\sqrt{n}\) est rationnel. On peut alors trouver une fraction \(A/B\), avec \(A\) et \(B\) entiers positifs, telle que:
\[ n = \left(\frac{A}{B} \right)^2. \]
Cette égalité peut se réécrire ainsi:
\[ \frac{A}{B} = \frac{nB}{A}.\]
Il s’agit là d’une égalité entre deux nombres rationnels qui ne sont pas entiers. Leurs parties fractionnaires sont donc elles aussi égales, ce qui signifie qu’il existe deux entiers positifs \(a,b\) tels que:
\[ \frac{b}{B} = \frac{a}{A} \]
et que de plus \(a < A\) et \(b < B\). Mais la dernière égalité est équivalente à:
\[ \frac{a}{b} = \frac{A}{B}. \]
On a donc trouvé une nouvelle fraction qui représente \(\sqrt{n}\), avec un numérateur et un dénominateur strictement plus petits que ceux de \(A/B\). En continuant ainsi, on obtient des suites infinies et strictement décroissantes d’entiers positifs, ce qui est absurde. \(\sqrt{n}\) est donc irrationnel…

Retour aux cordes

Pour terminer, voici la réponse à la question que je vous ai posée au début de ce billet:

Théorème
Le nombre de régions en lesquels l’intérieur d’un cercle se trouve décomposé par les cordes qui joignent \(n\) points du cercle (tels qu’il n’y ait pas \(3\) cordes qui passent par le même point intérieur au cercle) est égal à:
\[{n-1 \choose 0} + {n-1 \choose 1} + {n-1 \choose 2} + {n-1 \choose 3} + {n-1 \choose 4}. \]

Ici \({n-1 \choose k}\) désigne le nombre de sous-ensembles à \(k\) éléments d’un ensemble à \(n-1\) éléments.

Comment prouver ce théorème? La méthode présentée dans le livre consiste à numéroter d’abord les points pris sur le cercle de \(0\) à \(n-1\), en respectant leur ordre circulaire, puis à associer à chaque région une «étiquette», qui est un sous-ensemble ayant au plus \(4\) éléments de l’ensemble \(\{1, 2, \dots, n-1\}\). La méthode d’association des étiquettes est indiquée par les auteurs sur la figure suivante:

Par exemple, pour les petites valeurs de \(n\) considérées plus haut, on obtient les codages suivants des régions (la région hachurée se voyant associer le sous-ensemble vide) :

 

Le point-clé est que de cette manière on obtient une bijection entre régions et sous-ensembles ayant au plus \(4\) éléments de l’ensemble \(\{1, 2, \dots, n-1\}\). Comme pour \(n \leq 5\), on obtient ainsi tous les sous-ensembles de \(\{1, 2, \dots, n-1\}\), cela explique pourquoi on trouve alors exactement \(2^{n-1}\) régions ⁷En effet, un ensemble \(E\) ayant \(n-1\) éléments a exactement \(2^{n-1}\) sous-ensembles. Pour le voir, on peut penser à la manière suivante de se donner un sous-ensemble de \(E\): on marque chaque élément du sous-ensemble d’une croix \(X\) et chaque élément qui n’en fait pas partie d’un rond \(O\). Il y a autant de sous-ensembles de \(E\) que de manières d’associer des croix et des ronds à ses éléments. Mais pour chaque élément, il y a \(2\) choix, et ces divers choix sont deux à deux indépendants, ce qui montre qu’il y en a bien \(2^{n-1}\) en tout.…

Êtes-vous d’accord avec moi que cela ferait un joli thème de réflexion dans un club mathématique de lycéens ⁸Bien sûr, il faudrait d’abord faire un échauffement avec les coefficients binomiaux. Le livre de Conway et Guy en propose quelques-uns. ?