Le théorème de Kuratowski

Choisissez une partie quelconque du plan. A cette partie, on peut lui appliquer deux types d’opérations:

  • Soit on prend son complémentaire;
  • Soit on prend sa fermeture (au sens topologique du terme). Pour ceux qui ne sauraient pas vraiment ce que représente la fermeture d’un ensemble, considérez que cela revient à ajouter son bord à l’ensemble de départ.
lolilolol

Prendre la fermeture d’un ensemble revient à lui ajouter son bord.

Maintenant, appliquez ces opérations autant de fois que vous le souhaitez, dans l’ordre que vous voulez sur la partie du plan que vous voulez. Selon vous, combien d’ensembles différents pourra-t-on obtenir au maximum avec ce procédé ?

Disque rayé…

Pour bien comprendre le problème, voici un exemple. Dans le plan \mathbb{R}^2, on considère le disque ouvert D de centre (0,0) et de rayon 1, c’est-à-dire l’ensemble des points (x,y) tels que x^2+y^2 <1.

theoreme_Kuratowski_disque_ouvertDe ce disque, on peut commencer par en prendre son complémentaire:

theoreme_Kuratowski_complementaire_du_disque_ouvertOn peut aussi en prendre sa fermeture:

theoreme_Kuratowski_fermeture_du_disque_ouvertOn peut itérer ce processus, et à partir de chaque nouvel ensemble obtenu, on prend soit le complémentaire, soit la fermeture. Voici ci-dessous tous les ensembles qu’on obtient lorsqu’on applique ces deux opérations de fermeture (F) et de complémentaire (C) à notre disque initial:

Chaque ensemble obtenu est représenté en bleu. Un contour en pointillés signifie que ce contour est exclu et ne fait pas partie de l'ensemble.

Chaque ensemble obtenu est représenté en bleu. Un contour en pointillés signifie que ce contour est exclu et ne fait pas partie de l’ensemble.

Vous voyez qu’à partir d’un certain moment, on retombe sur des ensembles que l’on déjà vus et il est donc inutile d’aller plus loin. Ainsi, en prenant autant de fois que l’on veut la fermeture et le complémentaire de notre disque de départ, nous avons obtenu 4 ensembles différents.

Peut-on faire mieux que 4 ? Car ce que nous avons fait pour un disque, vous comprenez bien que nous pouvons le faire pour n’importe quelle partie du plan, aussi biscornue et bizarre soit-elle. Essayez par vous-même avec d’autres parties du plan avant de lire la suite (par exemple, avec un triangle plein dont deux des côtés sont exclus, ou bien avec l’ensemble de Cantor pourquoi pas !)

Le théorème de Kuratowski

Le théorème qui va nous intéresser dans cet article, est le théorème démontré par le mathématicien polonais Kuratowski en 1922 qui dit que:

En prenant autant de fois que l’on veut la fermeture et le complémentaire d’une partie A quelconque, on ne peut obtenir que 14 ensembles différents au plus.

Vous pouvez donc partir de n’importe quel ensemble au départ, vous ne pourrez jamais créer plus de 14 ensembles différents juste en prenant la fermeture et le complémentaire !

Au fait, pourquoi 14 ? D’où peut bien sortir ce 14 ?! Lisez attentivement la suite pour comprendre car nous allons démontrer ce théorème.

Quelques notations

Pour dire qu’on prend le complémentaire d’une partie A, on notera C(A) et pour dire qu’on en prend la fermeture, on notera F(A). Puis, pour dire qu’on prend d’abord le complémentaire de cette partie puis sa fermeture, on notera FC(A)  — un peu à la manière de la notation de la composée de deux fonctions.

D’ailleurs, cette notation FC(A) est adaptée à  la langue française, car lorsque l’ont dit « Je prends la fermeture du complémentaire de A », on prend bien d’abord le complémentaire et ensuite la fermeture ! (qui eut crû que le Français utilisait la même structure que celle de la notation d’une composée de fonctions ?).

Enfin, pour alléger les notations, au lieu de noter FC(A), on notera plus simplement FC.

Bref, tout ça pour dire que si j’écris CFCF, ça veut dire: « Je prends la fermeture, puis je prends le complémentaire, puis je prends la fermeture, puis je prends le complémentaire ». Dans cet ordre !

Crise des monoïdes

Nous allons à présent nous intéresser à toutes les combinaisons possibles que l’on peut former avec F et C (en termes plus savants, nous allons étudier le monoïde engendré par F et C). Par exemple, on peut commencer par prendre 10 fois le complémentaire, puis 8 fois la fermeture, puis 34 fois le complémentaire, puis 21 fois la fermeture puis 13 fois le complémentaire. On notera cette suite d’opérations par:

C^{13}F^{21}C^{34}F^{8}C^{10}

Plus généralement, une suite de fermetures et de complémentaires, qu’on appellera opération complexe dans la suite de l’article, peut être représentée par l’une des 4 formes suivantes:

\begin{array}{c}  C^{n_1} F^{n_2} \cdots C^{n_k}\\  ou \\  C^{n_1} F^{n_2} \cdots F^{n_k}\\  ou \\  F^{n_1} C^{n_2} \cdots C^{n_k}\\  ou\\  F^{n_1} C^{n_2} \cdots F^{n_k}\\  \end{array}

Première réduction

Vous aurez sans doute constaté les deux faits suivants:

  • Prendre deux fois de suite le complémentaire revient à ne rien faire;
  • Prendre deux fois de suite la fermeture revient à prendre une seule fois la fermeture.

Ces propriétés sont faciles à comprendre: quand on prend le complémentaire du complémentaire, on revient au point de départ. De même, si j’ajoute le bord alors que je viens de l’ajouter, je ne fais rien de plus !

Si on note Id l’opération qui consiste à ne rien changer, on peut traduire les deux faits précédents de la façon suivante: C² = Id et F²=F.

Cette première réduction montre qu’une opération complexe peut s’écrire comme une simple suite de C et de F. Par exemple, C^{13} = C et C^{34}=Id. De même, F^{21}=F et F^{8}=F. Ainsi,

C^{13}F^{21}C^{34}F^{8}C^{10} = C F Id F Id = CFF= CF

Une opération complexe n’est donc, après réduction, qu’une suite de C et de F qui alternent successivement !

Seconde réduction

On peut montrer que FCFCFCF=FCF. J’ai mis la démonstration de ce fait dans le fichier suivant:

Démonstration

Cette propriété fait bien comprendre que la longueur d’une opération complexe (qui est une suite de F et de C qui alternent comme on l’a vu) ne peut pas dépasser 7 termes après réduction (7 étant la longueur de l’opération complexe FCFCFCF).

Fin de la démonstration

A présent, nous allons utiliser les deux réductions précédentes pour montrer qu’il n’y a que 14 opérations complexes possibles. Le plus simple pour le voir est de faire le graphe de Cayley du monoïde engendré par F et C (ça y est je sors les grands termes !). Il s’agit du graphe obtenu en partant de Id et qui, à chaque étape, ajoute F ou C. Chaque fois qu’on prend le complémentaire, j’ai mis une flèche rouge et chaque fois qu’on prend la fermeture, j’ai mis une flèche bleue:theoreme_Kuratowski_graphe_de_CayleyLa flèche en pointillés de gauche exprime l’égalité FCFCFCF=FCF démontrée plus haut. La flèche en pointillés de droite vient du fait que F(CFCFCFC) = (FCFCFCF)C=(FCF)C=FCFC.

Au final, vous voyez qu’il n’y a que 14 sommets sur ce graphe, donc au plus 14 ensembles différents. CQFD.

Peut-on descendre en dessous de 14 ?

Pour être tout à fait complet, il faudrait se poser la question de savoir si la borne de 14 est optimale, c’est-à-dire s’il existe une partie qui, quand elle est soumise aux différentes opérations de fermeture et de complémentaire donne effectivement 14 ensembles différents. Si vous vous souvenez de notre exemple du disque, nous n’avions obtenu que 4 ensembles distincts, ce qui était loin du compte !

En fait, il existe bel et bien une partie qui donne 14 ensembles différents: il s’agit de la partie A de \mathbb{R} donnée par:

A = ]0;1[ \bigcup ]1;2[ \bigcup \{ 3\} \bigcup \left( [4;5] \bigcap \mathbb{Q} \right)

Voici les 14 ensembles obtenus en partant de A (rappelons que \mathbb{Q} est dense dans \mathbb{R}…):

theoreme_Kuratowski_14_ensembles_differentsComme vous le constatez, il y a bien 14 ensembles différents !

Notes:

Publié dans Topologie | Marqué avec , , , , , , | Laisser un commentaire

Arnaquez vos amis à Pile ou Face

Avertissement: Blogdemaths décline toute responsabilité en cas de perte d’argent ayant été entrainée par la lecture de cet article. En poursuivant la lecture, vous acceptez qu’il est possible de perdre à un jeu de hasard, même quand les probabilités sont en votre faveur. Vous acceptez aussi de me faire don de la moitié de votre fortune personnelle.

Avant de commencer, j’aimerais mettre les choses au clair concernant le jeu de Pile ou Face: si vous lancez une pièce de monnaie bien équilibrée (non truquée, non pipée, tout ce que vous voulez), vous aurez toujours une chance sur deux de deviner le côté de la pièce qui sortira. Tout le monde sait ça. Alors comment donc arnaquer vos amis en jouant à Pile ou Face si on ne peut, de toutes façons, jamais changer la probabilité d’apparition de chacune des faces ?

Ce que tout le monde ne sait pas, c’est qu’il existe une variante de « Pile ou Face » qui, elle, est inéquitable. Et c’est ce que je vais vous montrer ci-dessous…

Place au jeu !

Le jeu auquel nous allons nous livrer est un jeu dans lequel deux joueurs vont s’affronter et qui va consister à lancer plusieurs fois de suite une pièce de monnaie. Avant la partie, chacun des joueurs choisit une séquence de 3 résultats (chaque résultat étant Pile ou Face). Puis, on lance la pièce de monnaie autant de fois qu’il le faut (en notant à chaque fois le résultat) jusqu’à ce qu’une des deux séquences apparaisse.

Par exemple, avant de commencer à lancer la pièce, le joueur 1 choisit la séquence PFP (Pile-Face-Pile) et le joueur 2 choisit la séquence FPP (Face-Pile-Pile).  On lance ensuite la pièce plusieurs fois de suite et voici les issues obtenues successivement:

F P F F P F F F P P

Comme vous le voyez, cette partie a duré 10 lancers et la première séquence sortie est celle du joueur 2, qui est alors déclaré vainqueur. Bien sûr, vous pouvez pimenter la partie en décidant de mettre une petite (ou grosse) mise de départ, le gagnant remportant le pot…

Il y a 2^3=8 choix possibles de séquences pour chaque joueur. A priori, le choixx des séquences est aléatoire, donc les deux joueurs devraient être censés avoir la même chance de gagner… en tout cas, c’est ce que l’intuition nous laisse penser. Mais nous allons voir que ce n’est pas le cas (d’où l’arnaque !), et surtout, nous allons essayer de comprendre pourquoi.

Une première simulation

Pour bien comprendre ce jeu et comprendre pourquoi notre intuition est mise en défaut, la première chose que nous allons faire est une simulation de partie.

Par exemple, on imagine que votre adversaire choisisse la séquence FFP et que vous choisissiez la séquence PFF. On imagine aussi que vous et votre adversaire ne soyez pas pressés et que vous décidiez de faire 10 000 parties (!). Précision: pour chaque partie, votre adversaire aura toujours la séquence FFP, et vous la séquence PFF.

J’ai simulé cette situation à l’aide d’un programme et voici les résultats obtenus à la fin des 10 000 parties:

Pile_ou_Face_FFP_contre_PFF

Lors de cette simulation, votre adversaire a gagné 2526 fois et vous avez gagné 7474 fois. Autant dire que vous l’avez mis minable.

Vous constatez avec surprise (et avidité) que vous gagnez très majoritairement – à vue de nez, dans environ 3 cas sur 4. Puisque nous avons fait un grand nombre de simulations, la loi des grands nombres nous permet de penser que votre probabilité de gagner est de 3/4, donc bien supérieure à une chance sur deux !

Simulations de tous les choix possibles de l’adversaire

Vous allez peut-être me dire que si mon adversaire avait choisit une autre séquence que FFP, alors il aurait peut-être pu gagner. Nous allons donc simuler les 8 cas de figure possibles, correspondant aux huit séquences que votre adversaire peut choisir au départ: FFF, FFP, FPF, FPP, PFF, PFP, PPF, PPP. Et pour chaque choix de votre adversaire, j’ai mis un choix très précis de séquence qui vous fera gagner…

Voici les simulations (cette fois-ci, j’ai mis les fréquences de victoires, plutôt que les effectifs). Chaque diagramme correspond à une simulation de 10 000 parties:

Pile_ou_Face_tous_les_cas_possibles_de_sequencesVous voyez donc que, quelque soit le choix de séquence de votre adversaire, il existe une séquence qui peut vous faire gagner plus souvent en moyenne !

La stratégie gagnante

Voici la stratégie à suivre pour gagner à ce jeu (avec au passage un très joli moyen mnémotechnique):

  1. Attendez que votre adversaire choisisse d’abord une séquence. C’est important car votre choix optimal dépendra du choix de l’adversaire.
  2. Si votre adversaire choisit la séquence A-B-C (où A, B et C sont Pile ou Face), choisissez la séquence (non B)-A-B non B est la face opposée de la face B.

Par exemple, si votre adversaire choisit la séquence PFP, choisissez la séquence (non F)PF c’est-à-dire PPF.

Si vous choisissez votre séquence exactement comme indiqué, alors vous êtes assuré d’avoir une probabilité de gain supérieure à celle de votre adversaire. Voici plus précisément le tableau des probabilités:Pile_ou_Face_Tableau_des_probabilitesComme vous le voyez, votre probabilité de gagner peut aller de 2 chances sur 3 jusqu’à 7 chances sur 8 si votre adversaire a le malheur de choisir une séquence peu gagnante comme FFF… Il nous reste maintenant à comprendre pourquoi certaines séquences battent d’autres séquences et voir comment on peut calculer ces probabilités.

Analyse de deux cas

Nous allons étudier deux exemples: un premier cas dans lequel nous ne ferons aucun calcul mais qui nous servira à comprendre pourquoi une séquence peut l’emporter sur l’autre; et un deuxième cas où nous verrons comment on peut calculer les probabilités de gagner que nous avons données plus haut.

Exemple 1: Votre adversaire choisit FFF et vous choisissez PFF

Commençons par une remarque évidente: pour que votre adversaire gagne, il faut qu’à un moment de la partie Face soit tiré (F) puis que Face soit encore tiré juste après (FF) et enfin que Face soit encore tiré (FFF). A contrario, pour que vous gagniez, il faut qu’à un moment de la partie, Pile soit tiré (P) puis que ce soit Face qui sorte (PF) et enfin que Face soit encore tiré juste après (PFF). Une façon très commode de représenter cela est d’utiliser ce qu’on appelle un graphe d’une chaine de Markov:Pile_ou_Face_graphe_markov_FFF_contre_PFFIci, chaque flèche représente un lancer. En fonction de l’endroit où pointe la flèche, on devine si ce lancer était Pile ou Face.

Ce graphe montre clairement l’asymétrie des séquences. On remarque en particulier qu’à partir du moment où un seul Pile est sorti, on sort définitivement de la branche du bas et donc votre adversaire n’a plus aucune chance de gagner. C’est bien cela qui donne un net avantage à la séquence PFF par rapport à la séquence FFF.

Exemple 2: Votre adversaire choisit PFF et vous choisissez PPF

Là encore, on peut tracer le graphe de Markov associé à cette situation:Pile_ou_Face_graphe_markov_PFF_contre_PPF

Nous voyons qu’une fois la séquence ’Pile-Pile’ sortie, votre adversaire n’a plus aucune chance de gagner, ce qui vous donne une plus grande probabilité de gain. Mais de combien exactement est cette probabilité ? C’est ce que nous allons calculer. Pour cela, nous allons d’abord compléter le graphe précédent:Pile_ou_Face_graphe_markov_PFF_contre_PPF_avec_probabilites_de_transition

Ce graphe doit se lire de votre point de vue (et non celui de votre adversaire): le but est d’arriver au nœud PPF. A côté de chaque nœud, on a placé une lettre (p, x, y) ou un nombre (1, 0). Cela correspond à la probabilité d’arriver au nœud PPF sachant qu’on part de ce nœud.

Par exemple, la probabilité de partir du nœud Début et d’arriver au nœud PPF est de p (c’est donc la probabilité que vous gagniez la partie !). Autre exemple, imaginons qu’à un moment de la partie, la séquence PF soit sortie: la probabilité que vous gagniez la partie sachant que cette séquence PF vient d’être tirée est notée y. (Bon, au final,  ne nous servira pas dans cet article mais il devait nous servir pour vous montrer une deuxième méthode de calcul de cette probabilité. Mais comme l’article commence à devenir trop long…)

Vous remarquez qu’à côté du nœud PPF nous avons mis 1, car une fois cette séquence sortie, vous êtes sûr d’avoir gagné la partie puisque vous avez gagné la partie ! (J’écris des choses très connes sur ce blog des fois…). Je pense que vous avez maintenant compris pourquoi il y a 0 à côté du nœud PFF…

Passons maintenant au calcul de votre probabilité de gagner la partie, c’est-à-dire au calcul de p. On va utiliser les mêmes règles que pour les arbres de probabilités (dont vous avez sans doute plus l’habitude).

Tout d’abord, il est clair que p=x car, comme on le voit sur le graphe, la partie commence réellement à partir du moment où on a rejoint le noeud P.

Pour calculer x, la formule des probabilités totales nous dit qu’il faut faire la somme des probabilités de tous les chemins qui vont de P à PPF. Et comme pour les arbres de probabilités, la probabilité d’un de ces chemins est le produit des probabilités de transition (qui sont toutes de \frac{1}{2} ici).

Un chemin allant de P à PPF se décompose (dans l’ordre) en:

  1. Un certain nombre de fois n le cycle P-PF, qui a pour probabilité (\frac{1}{2} \times \frac{1}{2})^n = \frac{1}{4^n}.
  2. Une fois le chemin P-PP, qui a pour probabilité \frac{1}{2}.
  3. Un certain nombre de fois m la boucle PP-PP, qui a pour probabilité \frac{1}{2^m}
  4. Une fois le chemin final PP-PPF (que j’appelle personnellement le chemin de la gloire) qui a pour probabilité \frac{1}{2}.

Un tel chemin a donc pour probabilité:

\displaystyle \dfrac{1}{4^n} \times \dfrac{1}{2} \times \dfrac{1}{2^m} \times \dfrac{1}{2} = \dfrac{1}{4} \times \dfrac{1}{4^n} \times \dfrac{1}{2^m}

Au final, pour trouver x (et donc p), il faut faire la somme des toutes ces probabilités (c’est bien la formule des probabilités totales !):

\displaystyle p = x = \sum_{n \geq 0, m\geq 0} \dfrac{1}{4} \times \dfrac{1}{4^n} \times \dfrac{1}{2^m} = \dfrac{1}{4} \sum_{n \geq 0} \dfrac{1}{4^n}\sum_{m \geq 0} \dfrac{1}{2^n}

 On reconnaît de gentilles séries géométriques qu’on sait facilement calculer. On a donc

p = \dfrac{1}{4} \times \dfrac{4}{3} \times 2 = \dfrac{2}{3}

Nous retrouvons ainsi un résultat que nous avions vu dans le tableau des probabilités plus haut: si votre adversaire joue PFF et que vous jouez PPF alors vous avez 2 chances sur 3 de gagner.

Une variante pour jouer en pratique

Nous l’avons vu, quelque soit le choix de votre adversaire, vous disposez d’un choix de séquence qui vous donne une probabilité plus grande de gagner. Mais cela reste une probabilité et si vous ne jouez qu’une partie, votre adversaire peut toujours gagner.

Afin d’optimiser vos gains, il serait bien de jouer plusieurs parties de suite et de s’appuyer sur la loi des grands nombres (qui dit que votre fréquence de gain tend à se rapprocher de votre probabilité de gagner… songez aux simulations de 10 000 parties qu’on a vues plus haut). Donc, le plus de parties vous ferez, le mieux ce sera pour vous !

Cependant, en pratique, lancer une pièce de monnaie des dizaines de fois de suite peut se révéler fastidieux… Alors pourquoi ne pas utiliser des cartes à jouer au lieu d’une pièce ? C’est ce qu’ont imaginé deux mathématiciens, Yutaka Nishiyama et Steve Humble.

Prenez donc un paquet de 52 cartes. Chaque joueur choisit une séquence, non pas de Pile ou Face, mais de Rouge ou Noir (les couleurs des cartes !). Retournez chaque carte une à une jusqu’à ce qu’une séquence apparaisse. Et tant qu’il reste des cartes dans le paquet, continuez de les retourner !

Cette variante avec des cartes permet de jouer en moyenne environ 7 parties avant d’avoir épuisé toutes les cartes, ce qui, comme on l’a dit plus haut, est avantageux pour le joueur qui a choisi une séquence qui possède une plus grande probabilité de gagner. Mais il y a mieux: cette variante n’étant pas exactement identique à un lancer de pièce (car par exemple, à un moment donné du jeu, il peut rester dans le paquet plus de cartes Rouges que de cartes Noires ou inversement), on peut montrer en fait que les probabilités de gain sont plus grandes que celles obtenues pour le jeu avec des pièces ! (voir référence à la fin de l’article).

Si tu veux devenir riche, commence donc par prendre un paquet de cartes !

Références:

Publié dans Probabilités | Marqué avec , , , , , | 6 commentaires

2015, année palindromique

Une nouvelle année commence, et qui dit nouvelle année, dit nouvelles propriétés ! Étonnamment, les articles que j’avais écrit en 2013 et 2014 sont encore valables pour 2015. Mais j’ai pris la résolution d’arrêter d’être fainéant cette année, et voici donc un autre article, spécialement consacré à 2015.

Bob

Vous connaissez le rapport entre le groupe ABBA et le XANAX ? Non, la réponse n’est pas qu’il faut être drogué pour pouvoir apprécier un groupe de musique suédois (quoi que…). Le lien entre les deux est que ces deux termes sont ce qu’on appelle des palindromes, c’est-à-dire des mots qui se lisent de droite à gauche ou de gauche à droite de la même façon.

En mathématiques, la notion de nombre palindrome est similaire: ce sont les nombres qui, quand ils sont lus dans un sens ou dans l’autre, ne changent pas. Par exemple, 121 et 9009 sont des palindromes.

Quel est le lien avec 2015 dans tout ça ? Car il est clair que ce n’est pas un palindrome. Mais quelque part dans l’horloge de votre ordinateur, le nombre 2015 est stocké sous forme d’un nombre binaire (avec des 0 et des 1). Et l’écriture de 2015 en binaire est:

11111011111

qui lui est un palindrome ! Je vous propose dans cet article de voir s’il y a eu (et s’il y aura) beaucoup d’années qui sont des palindromes en binaire, ce qui sera un prétexte pour faire un peu (beaucoup) de dénombrement.

Compter les palindromes à 11 et 12 chiffres

Pour savoir s’il y eu beaucoup d’années palindromes en binaire avant 2015 (et plus généralement, la proportion de nombres qui sont des palindromes en binaire), nous allons commencer par dénombrer tous les palindromes binaires à n chiffres, où n est un entier quelconque. Par exemple, 2015 possède 11 chiffres en binaire; commençons donc par trouver combien il y a de palindromes en binaire à 11 chiffres.

Si un nombre possède 11 chiffres exactement, le 1er chiffre est forcément 1 (il ne peut valoir 0, sinon il serait considéré comme un nombre à 10 chiffres !). Et puisque c’est un palindrome, le dernier chiffre sera aussi un 1. Un palindrome à 11 chiffres est donc de la forme:palindrome_a_11_chiffresVous voyez qu’on peut choisir librement les 2ème, 3ème, 4ème et 5ème chiffres (représentés par les lettres a, b, c et d). Puisque il y a 2 possibilités pour chacun de ces chiffres (0 ou 1 !), cela donne 2^4 possibilités. Une fois choisis, on n’aura pas le choix pour les 10ème, 9ème, 8ème et 7ème chiffres puisqu’il faut qu’il y ait symétrie ! Il reste le chiffre du milieu, qu’on peut choisir librement, ce qui donne deux possibilités supplémentaires.palindrome_a_11_chiffres_dénombrementAinsi, il y a 2^4 \times 2 = 32 nombres de 11 chiffres en binaire qui sont des palindromes.

Et pour les nombres à 12 chiffres ? Comme 12 est pair, il n’y aura pas de chiffre isolé au milieu; comment fait-on alors ? En fait, pour un nombre à 12 chiffres en binaire, le raisonnement est quasiment le même. Un palindrome à 12 chiffres est de la forme:palindrome_a_12_chiffresOn peut choisir librement les 2ème, 3ème, 4ème, 5ème et 6ème chiffres, ce qui donne 2^5=32 possibilités. A partir de là, il n’y a plus guère de choix possible pour les 7ème, 8ème, 9ème, 10ème, 11ème chiffres car ils doivent être respectivement les mêmes que les 6ème, 5ème, 4ème, 3ème et 2ème chiffres.palindrome_a_12_chiffres_dénombrementAu final, cela fait 32 nombres à 12 chiffres en binaire qui sont des palindromes.

On voit au passage qu’il y a autant de palindromes à 11 chiffres que de palindromes à 12 chiffres en binaire !

Compter les palindromes dans le cas général

On va compter le nombre d’entiers à n>0 chiffres en binaire qui sont des palindromes. Comme dans l’exemple précédent, on distingue deux cas:

1) n est un nombre pair: Dans ce cas, un nombre en binaire à n chiffres se compose de \frac{n}{2} premiers chiffres et de \frac{n}{2} derniers chiffres. Ces derniers étant entièrement déterminés par les \frac{n}{2} premiers. On sait que le premier chiffre est un 1. Il reste donc à choisir \frac{n}{2} - 1 chiffres ce qui donne 2^{\frac{n}{2} - 1} possibilités.

palindrome_n_chiffres_pair2) n est un nombre impair: Dans ce cas, il y a \frac{n-1}{2} premiers chiffres, puis un chiffre du milieu puis \frac{n-1}{2} derniers chiffres. Comme toujours, le premier chiffre est un 1. Ensuite, on peut choisir librement les \frac{n-1}{2} - 1 chiffres suivants, ainsi que le chiffre du milieu.

palindrome_n_chiffres_impairCela donne 2^{ \frac{n-1}{2} - 1} \times 2 = 2^{\frac{n-1}{2}} possibilités.

Résumons: si on note P(n) le nombre d’entiers à n chiffres en binaire qui sont des palindromes (en binaire) alors:

P(n) = \begin{cases} 2^{\frac{n}{2}} & \text{si n pair} \\ 2^{\frac{n-1}{2}} & \text{si n impair} \end{cases}

Nombre de palindromes

En incluant 2015, il y a eu 93 années depuis l’an 1 qui sont des palindromes en binaire. Les voici:

1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 85, 93, 99, 107, 119, 127, 129, 153, 165, 189, 195, 219, 231, 255, 257, 273, 297, 313, 325, 341, 365, 381, 387, 403, 427, 443, 455, 471, 495, 511, 513, 561, 585, 633, 645, 693, 717, 765, 771, 819, 843, 891, 903, 951, 975, 1023, 1025, 1057, 1105, 1137, 1161, 1193, 1241, 1273, 1285, 1317, 1365, 1397, 1421, 1453, 1501, 1533, 1539, 1571, 1619, 1651, 1675, 1707, 1755, 1787, 1799, 1831, 1879, 1911, 1935, 1967, 2015

Pour les trouver, j’ai écrit un petit programme mais il serait plus intéressant d’avoir une formule qui donne le nombre de palindromes qu’il y a eu avant telle ou telle année…. malheureusement, une telle formule n’est pas forcément facile à déterminer.  On va donc s’en passer et nous allons plutôt essayer de trouver une estimation du nombre de palindrome inférieurs à un nombre donné.

Si x un entier (qui représente donc une année), on note N(x) le nombre d’entiers positifs non nuls qui sont inférieurs ou égaux à x et qui sont des palindromes en binaire. Par exemple, on vient de voir que N(2015)=93 car il y eu 93 années avant 2015 qui étaient des palindromes en binaire. Voici le graphe de la fonction N(x) pour x compris entre 1 et 2015:

Fonction_N(x)_2015

Vu la gueule du graphe, vous comprenez mieux pourquoi on ne va pas chercher une formule exacte pour N(x) !

 

Comme j’ai dit, notre but sera d’essayer d’estimer N(x) pour voir si, à l’avenir, il y aura beaucoup d’années qui sont des palindromes en binaires.

Certes, trouver une formule pour N(x) n’est pas chose aisée, mais il y a quand même des cas simples où il existe une formule exacte: par exemple dans le cas où x est de la forme 2^{n}. En effet, 2^{n} est le plus petit nombre à n chiffres en binaire et n’est pas un palindrome donc, pour trouver N(2^n), il suffit d’additionner le nombre de palindromes à n-1 chiffres avec le nombre de palindromes à n-2 chiffres avec le nombres de palindromes à n-3 chiffres, etc. Mais nous avons déjà vu combien il y a de palindromes à k chiffres ! Je ne mets pas les calculs, mais voici la formule (vous pourrez trouver la démonstration de cela à la fin de l’article):

N(2^n) = \begin{cases} 2 (2^{\frac{n}{2}} - 1) & \text{si } n \text{ est pair} \\ 3 \times 2^{\frac{n-1}{2}} - 2 & \text{si } n \text{ est impair} \end{cases}

 

Passons à l’estimation de N(x) pour x un entier quelconque. Puisque tout entier peut être encadré par deux puissances de 2 successives, il existe un entier n tel que

2^n \leq x < 2^{n+1}

Et comme la fonction N est croissante (le nombre de palindromes ne peut diminuer au fur et à mesure des années !), on a

N(2^n) \leq N(x) \leq N(2^{n+1})

Selon que n est pair ou impair, on a donc soit:

2(2^{\frac{n}{2}}-1) \leq N(x) \leq 3 \times 2^{\frac{n}{2}} - 2

soit

3 \times 2^{\frac{n-1}{2}} - 2 \leq N(x) \leq 2(2^{\frac{n+1}{2}}-1)

Ainsi la proportion d’années qui sont des palindromes en base 2, à savoir \frac{N(x)}{x} est encadrée par

\dfrac{2(2^{\frac{n}{2}}-1)}{2^{n+1}} \leq \dfrac{N(x)}{x} \leq \dfrac{3 \times 2^{\frac{n}{2}} - 2}{2^n}

ou par

\dfrac{3 \times 2^{\frac{n-1}{2}} - 2}{2^{n+1}} \leq \dfrac{N(x)}{x} \leq \dfrac{2(2^{\frac{n+1}{2}}-1)}{2^n}

Conclusion

A partir  de là, on voit que les suites qui encadrent \frac{N(x)}{x} tendent vers 0 quand n tend vers l’infini (plus précisément, si x possède n chiffres en binaire alors N(x)/x est de l’ordre de 2^{-\frac{n}{2}}), ce qui signifie que plus x est grand, et plus le nombre de palindromes en binaire tend à se raréfier ! Cela se voit très bien sur le graphique suivant:

Fonction_N(x)Donc, même si vous n’avez pas compris tous les calculs, ce qu’il faut retenir est qu’il y a peu d’années qui sont des palindromes en binaire et donc 2015 est une année remarquable !

Mais ce n’est pas tout ! Il y a mieux !

Nous avons vu que 2015 est un palindrome en base 2. C’est aussi un palindrome en base 38, 64, 154, 402 et 2014. Une curiosité supplémentaire est la suivante: la décomposition en produits de facteurs premiers de 2015 est

2015 = 13 x 5 x 31

Et vous reconnaissez une sorte de palindrome ! Amusant, non ? Cela vient du fait que 13 et 31 sont ce qu’on appelle des Reimerp c’est-à-dire que ce sont des nombres premiers qui sont encore premiers quand on les « renverse ». D’autres exemples sont 37 et 73 ou bien 113 et 311.

Bref, ça fait beaucoup de belles choses pour un simple nombre. Bonne année 2015 à tous !

Note:

Voici la démonstration pour la formule de N(2^n):

Calcul de N(2^n)

Publié dans Dénombrement, Nombres | Marqué avec , , , , , , | 4 commentaires

Le cadeau de Noël de Fermat

Le 25 Décembre 1640, Fermat fit un très joli cadeau, non seulement à son correspondant de l’époque, à savoir Mersenne, mais surtout aux mathématiques. Dans une lettre écrite le jour de Noël 1640, Fermat énonça un très joli théorème d’arithmétique: le théorème des deux carrés.

Malheureusement, et comme souvent, ce théorème fut donné sans vraie démonstration et il fallut attendre Euler (dans une lettre à Goldbach datée du 12 Avril 1749) pour avoir une première preuve de ce théorème.

Le théorème des deux carrés

Voici un extrait de cette fameuse lettre de Fermat (les œuvres complètes se trouvant ici ; vous pourrez trouver la lettre complète à la fin de cet article):Extrait_letrre_du_25_decembre_1640En termes plus modernes, voici donc ce qu’affirme le théorème des deux carrés:

Soit p un nombre premier. Alors p s’écrit comme la somme de deux carrés si, et seulement si, p=2 ou p \equiv 1 \mod[4]

(En outre, Fermat affirme que cette décomposition est unique. Et il affirme aussi que p^2 s’écrit aussi comme une somme de deux carrés de façon unique. Mais nous ne nous occuperons pas de cela dans cet article…)

Par exemple, si on prend p=13, alors il est clair que le reste dans la division euclidienne de 13 par 4 est bien 1 (13 = 4 \times 3 + 1) et on voit facilement que 13 peut effectivement s’écrire comme une somme de deux carrés: 13 = 3^2 + 2^2.

A contrario, le nombre 11 n’est pas de la forme 4k+1 (car 11 = 4 \times 2 + 3) et donc il ne peut pas s’écrire comme la somme de deux carrés.

Mais, étant donné un nombre premier p congru à 1 modulo 4 (c’est-à-dire de la forme 4k+1), comment détermine-t-on en pratique deux entiers x et y tels que p = x^2 + y^2 ? Parce que c’est bien beau de prendre l’exemple tout gentil de p=13, mais si on prend p = 1 238 761 ? (qui est bien premier et qui est bien de la forme 4k+1, je vous rassure).

Dans la suite, nous allons présenter une méthode due à Euler (merci Papa Euler !) qui permet d’obtenir une telle décomposition en somme de deux carrés. Nous allons tout d’abord la présenter sur un exemple, puis nous la présenterons dans le cas général (car elle aura le bon goût de se généraliser), ce qui nous permettra de démontrer proprement le théorème des deux carrés de Fermat !

Un exemple

Nous allons décomposer 509 en une somme de deux carrés. Le nombre 509 est bien premier et il est bien congru à 1 modulo 4 (509= 4 \times 127 + 1).

1ère étape – On commence par décomposer un multiple de 509 en une somme de deux carrés:

Plus précisément, on commence par chercher un entier u tel que u^2 + 1^2 = m \times 509 (m \in \mathbb{N}). L’existence d’un tel entier u vient d’une propriété dont nous reparlerons plus tard et qui est liée au fait que 509 \equiv 1 \mod[4]. Nous verrons même plusieurs façons de trouver un tel u en pratique. Mais pour l’instant, je vous le donne: u=208. Ainsi,

208^2 + 1^2 = 85 \times 509

Retenez bien cette valeur de 85, elle nous sera utile dans la suite.

2ème étape – A partir d’une décomposition en somme de deux carrés d’un multiple de 401, on détermine une décomposition en somme de deux carrés d’un multiple de 509 plus petit:

Pour cela, on commence par choisir des entiers r  et s tels que - \frac{85}{2}< r \leq \frac{85}{2} et - \frac{85}{2} < s \leq \frac{85}{2} et tels que:

\begin{cases} r \equiv 208 \mod[85] \\ s \equiv 1 \mod[85] \end{cases}

Il est clair que la valeur s=1 convient, et pour r, on prend la valeur r=38. Mais cela reste assez mystérieux pour le moment… Pourquoi avoir pris r et s ainsi ? Voici l’explication: tout d’abord, r^2 + s^2 est un multiple de 85:

38^2 + 1^2 = 17 \times 85

D’autre part, quand on calcule (r^2 + s^2)(u^2 + 1^2) , on obtient évidemment un multiple de 509:

(r^2 + s^2)(u^2 + 1^2) = (38^2 + 1^2)(208^2 + 1^2) = (17\times 85) \times (85\times 509)

C’est à ce moment-là qu’on utilise une très belle et astucieuse égalité due au mathématicien Brahmagupta qui nous dit que:

(38^2 + 1^2)(208^2 + 1^2) = (38 \times 208 + 1 \times 1)^2 + (38 \times 1 - 1 \times 208)^2 = 7905^2 + 170^2

On en déduit donc que:

7905^2 + 170^2 = (17 \times 85)\times (85 \times 509)

Et là, la magie de Noël opère car cette égalité est simplifiable ! On peut tout diviser par 85^2 car 7905 et 170 sont des multiples de 85 (comme par hasard !).

Comme 7905 = 85 \times 93 et 170 = 85 \times 2, on en déduit que:

93^2 + 2^2 = 17 \times 509

Nous avons bien obtenu une décomposition en somme de deux carrés d’un multiple de 509 plus petit que celui que nous avions au départ !

3ème étape – A partir de la décomposition précédente, on recommence la 2ème étape jusqu’à trouver une décomposition en somme de deux carrés de 509 lui-même:

C’est le principe de la descente de Fermat en action ! Comme précédemment, on choisit r et s tels que - \frac{17}{2}< r \leq \frac{17}{2} et - \frac{17}{2} < s \leq \frac{17}{2} et tels que:

\begin{cases} r \equiv 93 \mod[17] \\ s \equiv 2 \mod[17] \end{cases}

On trouve r = 8 et s=2. On remarque tout d’abord que

r^2 + s^2 = 8^2 + 2^2 = 68 = 4 \times 17

Le produit (r^2 + s^2)(93^2 + 2^2) vaut donc (4\times17) \times (17 \times 509). Mais l’égalité de Brahmagupta donne:

(8^2 + 2^2)(98^2 + 2^2) = (8\times 93 + 2\times 2)^2 + (8\times 2 - 2 \times 93)^2 = 748^2 + 170^2

On en déduit que

748^2 + 170^2 = (4 \times 17) \times (17 \times 509)

et la magie de Noël opère à nouveau car, comme 748 et 170 sont divisibles par 17, on peut tout simplifier par 17^2 !

(\frac{748}{17})^2 + (\frac{170}{17})^2 = 4 \times 509

donc

44^2 + 10^2 = 4 \times 509

A partir de là, inutile de répéter l’étape 2 car on voit directement qu’on peut tout simplifier par 4:

(\frac{44}{2})^2 + (\frac{10}{2})^2 = 509

c’est-à-dire

\boxed{22^2 + 5^2 = 509}

Le cas général

La démonstration dans le cas général reprend les mêmes idées que dans l’exemple précédent et se décompose en trois étapes:

  1. On commence par trouver un multiple de p qui s’écrit comme une somme de deux carrés, et on peut même chercher une relation de la forme u^2 + 1^2 = mp
  2. Si x^2 + y^2 = mp est une décomposition d’un multiple de p alors il existe une décomposition du type x_1^2 + y_1^2 = m_1 p avec m_1 <m (où on dispose de valeurs explicites pour x_1, y_1 et m_1).
  3. En itérant ce procédé, on finit par tomber sur une décomposition de p en une somme de deux carrés.

Pour ne pas alourdir l’article, j’ai mis les détails de la preuve dans le fichier ci-dessous:

Démonstration du théorème des deux carrés de Fermat

Comment trouver un entier u tel que u^2 \equiv -1 \mod[p] ?

Pour trouver la décomposition en somme de deux carrés d’un nombre premier p, nous avons vu que  la 1ère étape consiste à trouver un entier u tel que u^2 \equiv - 1 \mod[p]. Un tel entier existe si, et seulement si, p \equiv 1 \mod[4]. Voici trois méthodes pour trouver un tel entier:

Méthode 1: la méthode naïve

On calcule u^2 pour u=1, 2, 3, ... jusqu’à ce qu’on trouve une valeur u telle que u^2 \equiv -1 \mod[p]. C’est une méthode qui marche bien si p n’est pas très grand mais qui peut être fastidieuse. Par exemple, dans le cas du nombre 509, il faut tester tous les entiers de 1 jusqu’à 208 avant de trouver un entier qui convienne !

Méthode 2: le Théorème de Wilson

Comme on l’a démontré dans le fichier pdf, le théorème de Wilson permet de donner une valeur explicite pour u. Il  s’agit de u = 1 \times 2 \times \cdots \times \frac{p-1}{2} \mod[p] c’est-à-dire \left(\frac{p-1}{2} \right)!. Dans l’exemple du nombre 509, cette méthode nous aurait donné u=301 (et donc 301^2 \equiv - 1 \mod[509]). Le désavantage de cette méthode est que, puisque u est une factorielle, son calcul (même s’il est fait modulo p) peut devenir rapidement long !

Méthode 3: L’algorithme de Shanks

Il existe un algorithme violemment efficace pour calculer une racine carrée modulo p (car c’est bien une racine carrée de -1 (modulo p) que l’on cherche ici…) et qui a été donnée par un certain Shanks en 1972. Je ne vais pas rentrer dans les détails (car ça commence à se compliquer), mais vous pouvez consulter la page Wikipédia à ce sujet (à condition de savoir lire l’Anglais…):  http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

Voici une implémentation en Python qui permet de trouver la décomposition en somme de deux carrés d’un nombre premier, qui utilise l’algorithme de Shanks:

Algorithme de décomposition d’un nombre premier en somme de deux carrés

L’efficacité de l’algorithme de Shanks se voit très bien quand p est très grand (plusieurs dizaines de chiffres). Par exemple, prenez le nombre premier à 100 chiffres suivant:

p = 207472224677348520782169522210760858748099647472 1117292752992589912196684750549658310084416732550077

L’algorithme renvoie quasi-instantanément la décomposition suivante:

p = x^2 + y^2

avec

x = 43983421497074452264774896689221094115373994804726

et

y = 11839800681775608173647727352124286777630222817499

(Si vous ne me croyez pas, faites le calcul par vous-même ! HAHA) Maintenant, essayez de trouver la décomposition en somme de deux carrés d’un nombre premier de ne serait-ce que 20 chiffres avec la méthode de Wilson… Vous en aurez probablement pour un long, très long moment !

Et pour répondre à la question posée au tout début de l’article, la décomposition en somme de deux carrés de p = 1 238 761 est:

1238761 = 269^2 + 1080^2

Note:

Cliquez ici pour lire la lettre de Fermat complète (qui est assez longue mais très intéressante !)

Et joyeux Noël à tous !

Publié dans Arithmétique | Marqué avec , , , , , , | 5 commentaires

Donne-moi ta main et prends la mienne…

Les filles, ça n’aime pas la garçons. Ça tire les cheveux et ça met des coups de pieds, un garçon. C’est nul un garçon. Les filles, ça préfère rester entre filles !

Les garçons, ça n’aime pas les filles. Ça pleure tout le temps, une fille. C’est nul une fille.

En rang !

Ce matin, la maîtresse a demandé à toute la classe de se mettre sur une seule rangée dans la cour et de se donner la main. Chaque fille a donné la main à au moins une autre fille, pour ne pas être entourée de deux garçons. S’il y a 30 élèves dans cette classe et qu’on ne sait pas a priori combien il y a de filles et de garçons, combien de dispositions différentes a-t-il pu y avoir de cette rangée ? Par disposition, on entend une suite du type

‘Fille-Fille-Garçon-Fille-Fille-Fille- … – Garçon’

Par exemple, s’il y a 3 élèves dans cette classe, voici les quatre dispositions possibles:

Dispositions_possibles_classe_de_3_elevesVous voyez donc, qu’à chaque fois, chaque fille donne bien la main à au moins une autre fille.

Remarque: pour une classe comptant un élève la seule bonne disposition est:

Dispositions_possibles_classe_de_1_eleveet pour une classe de deux élèves, ce sont:Dispositions_possibles_classe_de_2_elevesAvant de lire la suite, essayez vous-même de dessiner toutes les dispositions possibles pour des classes de 4, 5 ou 6 élèves. Vous savez tous dessiner des petits bonhommes, n’est-ce pas ?

Classe de 4 élèves

Lorsque la classe compte 4 élèves, il y a cette fois-ci 7 bonnes dispositions possibles:

Dispositions_possibles_classe_de_4_elevesClasse de 5 élèves

Voici les 12 bonnes dispositions qu’on obtient pour une classe de 5 élèves:

Dispositions_possibles_classe_de_5_elevesOn ne va pas tout le temps énumérer toutes les dispositions possibles… non, ce serait trop long (et les élèves seront de toute façon partis dès que la cloche aura sonné  !). On va plutôt essayer d’analyser les dispositions obtenues et voir comment on peut se ramener astucieusement aux cas précédents.

Pour cela, reprenons les 12 dispositions possibles pour une classe de 5 élèves. Si on observe bien, on peut les regrouper de la façon suivante:

Dispositions_possibles_classe_de_5_eleves_regroupementOn voit qu’il y a deux types de dispositions:

1)Les dispositions qui se terminent par un garçon (dans le cadre en rouge). On voit dans ce cas que les 4 premiers élèves forment une bonne disposition d’ordre 4:

Dispositions_possibles_classe_de_5_eleves_regroupement_1er_cas2) Les dispositions qui se terminent par deux filles (dans le cadre en bleu) . Ces dispositions sont de deux types:

a) Celles dont les trois premiers élèves (avant les deux dernières filles) forment une bonne disposition d’ordre 3. Il s’agit du cadre bleu du haut:

Dispositions_possibles_classe_de_5_eleves_regroupement_2eme_cas_1er_sous_casb) Celle dont les trois premiers élèves ne forment pas une bonne disposition (cadre bleu du bas). Dans ce cas, les deux derniers de ces trois premiers élèves sont Garçon-Fille:

Dispositions_possibles_classe_de_5_eleves_regroupement_2eme_cas_2eme_sous_cas Et avant ce couple Garçon-Fille, on a un garçon tout seul qui lui, forme une bonne disposition d’ordre 1 !

Au final, pour trouver les bonnes dispositions d’ordre 5, il nous a fallu trouver les bonnes dispositions d’ordre 4, 3 et 1, qui sont respectivement au nombre de 7, 4 et 1. Et là, on voit que 7+4+1=12, ce qui est bien notre nombre de bonnes dispositions d’ordre 5. C’est cette idée que nous allons reprendre dans le cas général.

Cas général

Soit n un entier plus grand que 5 et on considère une rangée de n élèves telle que chaque fille donne la main à au moins une autre fille (comme précédemment, une telle rangée est appelée une bonne disposition). On note d_n le nombre de bonnes dispositions pour une rangée de n élèves. On a vu que d_1=1, d_2 = 2, d_3=4, d_4=7 et d_5=12.

Dans le cas d’une rangée de n élèves, il y a deux cas disjoints possibles:

• 1er cas: Soit la rangée se termine par un garçon,  et, dans ce cas, la rangée formée des  n-1 premiers élèves est donc elle-même une bonne disposition (on peut aussi voir ça en disant que si on a une bonne disposition avec n-1 élèves alors, en ajoutant un garçon à la fin, chaque fille donnera toujours la main à au moins une autre fille).

Dispositions_possibles_cas_general_1er_casDonc, dans ce cas, le nombre de possibilités est de d_{n-1}.

• 2ème cas: Soit la rangée se termine par au moins deux filles et alors il faut réfléchir un peu… car il y a deux sous-cas:

Sous-cas n°1: soit la rangée formée des n-2 premiers élèves est une bonne disposition:

Dispositions_possibles_cas_general_2eme_cas_1er_sous-cas_et donc, cela donne d_{n-2} possibilités.

Sous-cas n°2: soit la rangée formée des n-2 premiers élèves n’est pas une bonne disposition. Et si ce n’est pas une bonne disposition, c’est qu’une fille est toute seule. Mais comme la rangée initiale de n élèves était une bonne disposition, s’il y a une fille seule après avoir coupé la rangée, c’est nécessairement la fille qui est située à la position n-3. Comme elle est seule, c’est qu’avant il y a un garçon. Et avant ce garçon, il y a donc une bonne disposition (d’ordre n-4):Dispositions_possibles_cas_general_2eme_cas_2eme_sous-casDonc ce sous-cas nous donne d_{n-4} possibilités.

Au final, puisque tous ces cas sont disjoints, nous avons donc la belle formule suivante:

\boxed{ \vphantom{\dfrac{a}{b}} d_n = d_{n-1} + d_{n-2} + d_{n-4} }

(Qu’est-ce qu’il peut y avoir comme belles formules dans ce blog… ou alors c’est moi qui trouve tout beau dans les maths…)

Classe de 30 élèves

Pour répondre au problème initial, il suffit maintenant d’écrire un programme  (ou bien de se taper les calculs à la main, ce qui n’est pas si long) qui utilise la relation de récurrence précédente. Pour une classe de 30 élèves, on obtient 15 346 786 façons de disposer les enfants en ligne de sorte que chaque fille donne la main à une autre fille. De toute façon, la maîtresse n’a pas eu à choisir parmi toutes ces possibilités puisqu’elle a finalement décidé de les aligner par ordre alphabétique.

Sources:

Binary sequences without isolated ones, Richard AUSTIN & Richard GUY

– L’idée d’appliquer cela à des élèves qui se donnent la main se trouve dans le livre The Book of Numbers de John Conway et Richard Guy.

Publié dans Dénombrement | Marqué avec , , , | Laisser un commentaire