Rediffusion d’un article publié en 2017

Démarrage trompeur

El 1ro marzo 2022 - Escrito por Patrick Popescu-Pampu Ver los comentarios (9)
Leer el artículo en

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 à $2^{n-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 [1]:

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 [2]. 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 [3]...

Êtes-vous d’accord avec moi que cela ferait un joli thème de réflexion dans un club mathématique de lycéens [4]?

Article édité par Emmanuel Jacob

Notas

[1] 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.

[2] Les nombres surréels ont été présentés sur ce site dans un article de Lisa Rougetet.

[3] 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.

[4] Bien sûr, il faudrait d’abord faire un échauffement avec les coefficients binomiaux. Le livre de Conway et Guy en propose quelques-uns.

Comentario sobre el artículo

Démarrage trompeur

le 28 de diciembre de 2017 à 10:05, par Arnaud Chéritat

Merci pour ce bel article.

Je ne connaissais pas la formulation de la solution comme une somme de nombres de combinaisons, je savais seulement que c’était un polynôme de degré 4.

C’est d’ailleurs l’unique polynôme de degré au plus 4 et qui prend successivement les valeurs 1, 2, 4, 8 et 16 pour les valeurs de 1 à 5 de la variable.

Notons l’ironie : cette suite, définie de façon bien naturelle, fait «semblant» de valoir 2^n. Non seulement ça mais la première valeur en désaccord ne diffère de 2^5 que de la plus petite valeur possible : un ! Et pour finir, elle vaut le polynôme de plus bas degré prenant les valeurs 2^n sur les 5 premiers entiers>0... C’est comme si la question était dotée d’une âme et que celle-ci n’avait d’autre occupation que de nous jouer des tours.

J’aime bien cette suite et la propose souvent en exercice ludique. On dénombre par récurrence (il faut savoir sommer n^k). On encore découvrir expérimentalement qu’en appliquant 4 fois l’opérateur «différences» on obtient une suite qui a l’air constante.
Répondre à ce message

Démarrage trompeur

le 2 de enero de 2018 à 13:07, par Antoine Chambert-Loir

Mes souvenirs de lycéen me disent que cette question faisait partie de l’épreuve de sélection au championnat de jeux mathématiques et logiques de 1988. Je ne me rappelle plus de l’intitulé exact (fallait-il trouver le polynôme, ou seulement sa valeur en $n=5$ ou $6$ ?).

Sinon, en manipulant l’opérateur de différence, on peut voir plus ou moins facilement d’autres phénomènes de ce genre, par exemple en cherchant un polynôme de degré $n$ qui coïncide avec $x \mapsto x^{n+1}$ sur $0,1,\ldots,n$ (je ne me rappelle plus ce que ça donne, il vaut probablement mieux appeler les polynômes de Bernoulli à la rescousse) ou (comme dans cet exemple, à peine généralisé), un polynôme de degré $n$ qui coïncide avec $x\mapsto 2^x$ sur $0,1,\dots,n$.
Répondre à ce message

Démarrage trompeur

le 3 de enero de 2018 à 17:27, par François Sauvageot

Oui, merci Patrick pour l’article. C’est un chouette sujet, mais il reste assez difficile. Cette combinatoire n’est plus trop à la mode et donnera donc du fil à retordre à des élèves de secondaire ... et même à des étudiant.e.s du supérieur !

Que ce soit les coefficients binomiaux (dont l’interprétation n’est pas vraiment donnée dans le secondaire) ou la dérivation discrète (qui est absente des considérations du secondaire), les bases sont fragiles. C’est d’ailleurs pourquoi, en MP*, je passe pas mal de temps sur l’opérateur $\Delta$ de Newton, ou dérivée discrète : $\Delta=\tau-Id$ : $P\mapsto P(X+1)-P$.

La base adaptée aux calculs avec $\Delta$ est celle des polynômes de Newton \[\Gamma_n={X\choose n}=\frac{X(X-1)\cdots(X-n+1)}{n!}\]
puisque $\Delta(\Gamma_{n+1})=\Gamma_n$, en parfaite analogie avec la base de Taylor $\frac{X^n}{n!}$ adaptée aux calculs avec la dérivée et donc le développement en série de Taylor.

On obtient rapidement le fait suivant pour un polynôme $P$ de degré $n$ :
\[P=\sum_{k=0}^na_k\Gamma_k\Longleftrightarrow\forall k\in[0;n]\,a_k=\Delta^k(P)(0)\]
puisque tous les $\Gamma_k$ sont nuls en 0, sauf $\Gamma_0$ qui y vaut 1.

Comme
\[\Delta^k=(\tau-I)^k=\sum_{i=0}^k(-1)^{k-i}{k\choose i}\tau^i\]
on en déduit que les coefficients de $P$ dans le développement en série de Newton est obtenu à partir des premières valeurs de $P$ sur les entiers de la façon suivante :
\[a_k=(-1)^k\sum_{i=0}^k(-1)^i{k\choose i}P(i).\]
Ce qui est remarquable est que cette construction est stable par élévation du degré ! Donc on peut faire de l’inter(extra)polation itérative à peu de frais : on cherche un polynôme de degré $n$ qui fait le job en s’adaptant aux $n+1$ premières valeurs constatées et ensuite, si on n’est pas satisfait, on augmente le degré en ne calculant qu’un coefficient de plus à chaque fois.

Ainsi, quand on cherche à deviner une formule que l’on espère polynomiale, on devrait enseigner qu’il faut chercher la décomposition dans la base des polynômes de Newton. C’est d’ailleurs comme ça qu’on peut trouver facilement des erreurs dans des reports dans des listes obtenues avec des formules polynomiales : apparait par linéarité une erreur qui, par itération de $\Delta$, fournit des coefficients binomiaux (correspondant au dévelopement de $X^n$ dans la base de Newton). Il faut aussi faire concorder les observations avec des valeurs de 0 à $n$. Ici on part de $n=2$ et on peut soit décaler de 2, soit commencer à $n=1$ en prenant la valeur 1 (c’est plus dur d’imaginer une valeur avec $n=0$).

Si $P(k)=b^k$, on trouve $a_k=(b-1)^k$. Il y a d’ailleurs un sujet sympa de l’X à ce propos (X 2011, filière MP, composition B) : accélération de convergence via la transformation d’Euler. Ici $b=2$ et donc les coefficients sont l’unité !
L’écart entre $P_4=\sum_{k=0}^4\Gamma_k$ et $2^X$ est donc donné par les termes manquants : $2^n-P_4(n)=\sum_{k=5}^n\Gamma_k(n)$. Pour $n=5$, on trouve $\Gamma_5(5)={5\choose 5}=1$. En fait on se balade sur la $n$-ème ligne du triangle de Pascal et on somme les cinq premiers termes, donc sur la cinquième ligne on ne néglige qu’un terme qui vaut 1.

Autrement dit quand on dit : $1$, $2$, $4$ ... on devrait penser directement $\Gamma_0$, $\Gamma_0+\Gamma_1$, $\Gamma_0+\Gamma_1+\Gamma_2$, etc. i.e. $1$, $n$, $\frac{n^2-n+2}2$, etc. tout en ayant en tête que la somme de la série $\sum\Gamma_k$ est $2^X$ !

Si $P(k)=k^{n+1}$, on peut en effet penser aux polynômes de Bernoulli puisque, par définition (ou presque) de ces polynômes, on a $\Delta(B_{n+1})=(X^{n+1})'=(n+1)X^n$, i.e. ce sont eux qui permettent de sommer des puissances $n$-èmes. Toutefois aucune formule simple ne m’est apparue en rédigeant ces lignes ...
Répondre à ce message

Démarrage trompeur

le 4 de enero de 2018 à 10:47, par Patrick Popescu-Pampu

Merci François pour ces explications très intéressantes, qui me semblent parfaites pour des ateliers de maths en licence !

Et bonne année !
Répondre à ce message

Typos

le 3 de enero de 2018 à 19:25, par François Sauvageot

Juste pour dire, la numérotation des figures est un peu étrange, peut-être pourrait-on les supprimer (3.12, 3.13 et la référence à 3.11 ...).

Et par ailleurs il manque le numéro 1 sur le sommet pour n=2 et l’étiquette 123 dans la figure pour n=5.
Répondre à ce message

Typos

le 4 de enero de 2018 à 10:49, par Patrick Popescu-Pampu

Cher François,

Tu as raison en ce qui concerne les nombres manquants dans les figures. Quant aux numéros de celles-ci, ce sont ceux du livre, ils permettront aux lecteurs intéressés de retrouver facilement l’endroit précis où les auteurs parlent de cet exemple.
Répondre à ce message

Démarrage trompeur

le 3 de enero de 2018 à 23:06, par aunryz

Peut-on raisonnablement donner le terme suivant d’une suite ?

Non !
Si le thème
comme c’est le cas dans la suite de l’article
n’est pas donné

D’ailleurs
la suite de la série 2,4,8,16,31
peut être 61 ; 57 ; 42 ou 56
et bien d’autres encore
(à vérifier en tapant ces valeurs)

Quant au démarrage trompeur
il n’existe que pour l’esprit informé
chez lequel certains chemins sont tracés
avec comme conséquence ce qui est joliment nommé
«entropie apparente»
par ceux qui s’intéressent à l’apparent chaos produit par certains automates cellulaires
au fonctionnement pourtant très simple.
Répondre à ce message
Démarrage trompeur

le 14 de septiembre de 2019 à 23:23, par M.F.H.

Il y a certes toujours différents choix possibles pour a(n+1), étant donné a(1..n) et rien d’autre. (Votre phrase «thème pas donné...» n’est pas claire... mais le «thème»(?) et la definition de la suite sont énoncés dès le début et à partir de là il n’y a aucune ambiguïté.)

Quand il s’agit de deviner a(n+1) sans aucune autre information, la réponse naturelle est celle qui correspond à la formule ou explication la plus simple. Sachant que le polynôme de plus bas degré qui passe par 1,2,4,8,16 (en n=0,...,4) donne comme par magie aussi P(5)=31, il est naturel de se baser sur cela pour «extrapoler» avec P(6)=57. (De manière équivalente on peut considérer la suite des premières, 2ndes, 3ièmes différences et extrapoler à partir de là.)
Répondre à ce message
Démarrage trompeur

le 30 de octubre de 2019 à 13:09, par funnix

Bonjour,

Je suis à la recherche de la démonstration qui démontre l’unicité de la bijection entre le codage de Conway et les figures codées sur la figure.

Est-ce que vous ou votre équipe avez un article qui démontre pourquoi l étiquette de chaque sous ensemble est constitué d’au plus 4 éléments de l ensemble 1 à n-1 ?

Cordialement,
Répondre à ce message

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexión | inscribirse | ¿contraseña olvidada?