Stirling 2 – Le retour

Sortez les popcorns et installez-vous confortablement dans votre siège. C’est l’heure des frissons.

Trailer

La scène se passe dans un grand manoir situé au milieu d’une forêt américaine. Un groupe de 10 jeunes personnes alcoolisées s’est réuni pour passer le week-end afin de célébrer les vacances de Printemps. Mais la nuit venue, des bruits étranges se font entendre dans les couloirs de la maison…

Ce que ces jeunes gens ignorent, c’est que 40 ans plutôt ce manoir a été le lieu d’un fait divers des plus sordides. Une famille toute entière avait alors été retrouvée ensevelie sous des hectolitres de beurre de cacahuète. La légende raconte depuis lors que cette maison est hantée par une cacahuète géante et communiste.

Comme dans tout bon film d’horreur américain, ces jeunes gens décident de se séparer en groupes en attendant que le jour se lève. On sait bien de toute façon que chaque groupe se fera tour à tour massacré lamentablement pendant la nuit, là n’est pas la question (j’ai même envie de dire que c’est uniquement pour cette raison qu’on a payé notre place de ciné). Ce qu’on peut se demander ici est plutôt: si ces 10 personnes décident de former trois groupes (chaque groupe n’étant pas nécessairement de la même taille),  de combien de façons peuvent-elles le faire ?

Nombre de Stirling de seconde espèce

On peut reformuler la question ainsi: "A  partir de 10 objets numérotés, combien y a-t-il de façons de former trois tas (non numérotés, les tas) ?". Mathématiquement, cette question s’énonce de la façon suivante: "Combien y a-t-il de partitions d’un ensemble à 10 éléments en 3 sous-ensembles ?".

Plus généralement, combien y a-t-il de partitions d’un ensemble à n éléments en k sous-ensembles ? Ce nombre de partitions possibles s’appelle nombre de Stirling de seconde espèce. On le note . Nous allons tenter de l’étudier dans cet article.

Quelques cas particuliers pour comprendre

Tout d’abord, il est clair que car il y une seule façon de former un groupe à partir d’une personne. De même, pour tout entier naturel n non nul. Ensuite, il est aussi évident que si k>n alors (comment voulez-vous former plus de groupes qu’il n’y a de personnes ?).

Voyons ce qu’il se passe pour quelques valeurs petites de n et de k:

Il y a trois façons de former deux tas à partir de trois objets numérotés donc S(3,2)=3.

S(4,3)=6

Enfin, voici une table des premières valeurs de S(n,k) représentées dans le jeu vidéo Minecraft (avec l’aide du mod Computercraft qui permet d’entrer des programmes codés en Lua):

Oui, je sais, j’aurais pu tout simplement faire un tableau sur Excel comme tout le monde mais je trouvais ça beaucoup plus amusant. Au passage, ce tableau nous donne la réponse à la question de départ: il y a 9330 possibilités de répartir les 10 jeunes gens en trois groupes.

Le calcul des termes de cette suite a été fait grâce aux propriétés que nous allons démontrer ci-dessous.

Etude de la suite S(n,k)

Un peu comme nous avions fait lorsqu’on nous avions calculé la probabilité que le Père Noel se trompe, nous allons déterminer une relation de récurrence satisfaite par la suite . Grossièrement, nous allons exprimer le nombre de partitions d’un ensemble à n éléments à partir du nombre de partitions d’un ensemble à n-1 éléments.

Considérons donc objets que nous devons répartir en groupes. Nous distinguons deux cas:

1. Si l’objet numéroté est tout seul dans son groupe, il faut donc répartir les autres objets dans les autres groupes, ce qui donne possibilités par définition.
2. Si l’objet numéroté n’est pas seul dans son groupe alors placer les objets revient à d’abord placer les premiers objets dans les groupes (ce qui donne possibilités) puis à placer l’objet dans un des groupes (ce qui donne possibilités). Au total, cela fait donc possibilités.

Puisque ces deux cas sont disjoints, nous avons donc prouvé que

Cette relation de récurrence permet de calculer facilement les valeurs de la suite à la manière du triangle de Pascal. En effet, cette relation dit que pour calculer le nombre situé dans la ligne et la colonne , il faut ajouter le nombre situé dans la case située en haut à sa gauche avec le produit de la case située juste au-dessus avec le numéro de la colonne. Dit comme cela, ça ne paraît sans doute pas très clair donc voici un schéma expliquant le calcul de :

Le calcul des nombres de Stirling est très proche du calcul des coefficients binomiaux dans le triangle de Pascal. Ici, S(10,4) = 255 + 3×3025 = 9330

Pour les flemmards qui préfèrent laisser à la machine le soin de calculer, sachez que cette relation de récurrence se programme très facilement. Voici le code en Lua pour calculer :

function Stirling(n,k)
if k>n then
return 0
elseif (k==n) or (k==1) then
return 1
else
return Stirling(n-1,k-1) + k*Stirling(n-1,k)
end
end

print("Stirling(10,3) = " .. tostring(Stirling(10,3))


Et voici le résultat:

Forme explicite de S(n,k)

Il est possible d’exprimer S(n,k) directement à partir de n et k. Plus précisément, voici la formule que nous allons démontrer (valable pour tout et pour tout ) :

Toutes les démonstrations que j’ai pu voir sur Internet utilisaient la formule du crible de Poincaré (encore appelée principe d’inclusion-exclusion). Mais on dispose d’une relation de récurrence vérifiée par cette suite, donc autant utiliser un raisonnement par récurrence. La démonstration par récurrence étant assez technique et lourde en notations, je l’ai mise dans le pdf ci-dessous. Je lance quand même une alerte au calcul imbitable… Je vous aurais prévenus !

Preuve de la formule explicite

Ouf !

Groupes numérotés

A présent, on suppose que les groupes ne sont plus indiscernables mais qu’ils sont chacun bien spécifiés. Par exemple, imaginons que nos 10 jeunes gens se séparent en trois groupes de la façon suivante: le groupe qui va se réfugier dans la cave (appelé groupe n°1), le groupe qui va se planquer au grenier (groupe 2) et le groupe qui va se cacher dans la chambre (groupe 3). Combien y a-t-il alors de façons de répartir ces 10 personnes dans ces trois groupes ? En fait, placer dix objets numérotés dans trois boites numérotées revient à compter le nombre de surjections d’un ensemble à 10 éléments dans un ensemble à 3 éléments.

Pour placer objets numérotés dans groupes numérotés, on commence par choisir une configuration de répartition de ces objets (ce qui donne possibilités) puis à choisir un numéro pour chacun des groupes (il y a possibilités, autrement dit autant de possibilités qu’il y a de permutations possibles de ces groupes). Ainsi, le nombre de façons de répartir objets numérotés n groupes numérotés est . C’est donc aussi le nombre de surjections d’un ensemble à n éléments dans un ensemble à k éléments.

En particulier, il y a possibilités de répartir nos 10 jeunes gens en trois groupes numérotés. Mais bon, le temps qu’ils essayent toutes les combinaisons, la cacahuète géante aura déjà eu largement le temps de tous les attraper…. Vraiment n’importe quoi cet article décidémment !

Note

Vous aurez sans doute reconnu dans le début de cet article une référence au sketch de Jean-Marie Bigard sur les films d’horreur.

Liens

Les nombres de Stirling sur Wikipedia.

Site officiel du langage de programmation Lua.

Site officiel du jeu Minecraft.

"Êtes-vous logique ?"

Il existe plein de tests de logique (à la con) dans les magazines ou sur Internet. La plupart de ces tests (qui revendiquent vouloir tester votre aptitude à la logique) ne sont en fait que des tests qui vous demandent de compléter des suites (de nombres, d’images ou de que sais-je encore d’autre). Je ne sais pas trop ce que mesurent ces tests (sans doute votre capacité à combler des trous… enfin compléter des suites !) mais une chose est sure, c’est qu’il ne mesurent pas votre logique au sens mathématique du terme.

Voici donc pour vous un test qui va réellement mesurer votre capacité à raisonner de manière logique.

Des cartes, des nombres et des couleurs

L’expérience à laquelle vous allez être confronté est la suivante. On dispose de quatre cartes. Chacune de ces cartes possède un nombre sur une face et une couleur sur l’autre face. On pose ces quatre cartes sur une table de telle sorte qu’une seule face de chaque carte est visible. Voici les quatre cartes en question:

Dans l’ordre, nous avons donc les cartes 3, 8, rouge, vert (oui, je pense aux daltoniens qui ont eux aussi le droit de faire ce test !). On considère l’affirmation suivante:

"Si une carte possède un nombre pair sur une face, alors elle est de couleur rouge sur l’autre face."

La question que je vous pose pour ce test est la suivante: quelle(s) carte(s) doit-on retourner pour déterminer si cette affirmation est vraie ou non ?

Attention, vous ne devez pas retourner de carte inutilement, ni oublier d’en retourner une ou sinon le test sera considéré comme échoué.

Prenez votre temps et réfléchissez bien avant de noter quelle(s) carte(s) vous retourneriez. Une fois votre choix effectué, lisez la suite.

Avec des si…

En logique mathématique, l’implication est une notion qui est souvent difficile à appréhender pour la plupart des gens. Le "Si… alors" a-t-il eu raison de vous ?

C’est l’heure de faire les comptes ! Si vous avez répondu:

- "Il faut retourner la carte 8 uniquement"

ou

- "Il faut retourner la carte 8 et la carte rouge"

alors je suis au regret de vous informer que vous vous êtes trompé. Ne vous en faîtes pas, vous n’êtes certainement pas les seuls à vous être trompé puisque ce test (appelé test de Wason du nom du psychologue qui l’a inventé) a un taux d’échec de l’ordre de 90% (c’est le pourcentage d’erreur qui en est ressorti lorsque Wason a soumis ce test à expérimentation auprès de gens).

Sans plus attendre, voici la solution.

Elémentaire mon cher Wason

Numérotons les cartes précédentes de 1 à 4: la carte n°1 est celle avec le 3, la carte n°2 est celle avec le 8, la carte n°3 est celle avec la face rouge et la carte n°4 est la carte avec la face verte.

Notons la proposition: "La carte i possède une face qui est un nombre pair" et la proposition: "La carte i possède une face qui est rouge". L’affirmation du test se traduit donc par:

Pour tout i, ()

Juste avant de poursuivre, rappelons qu’en logique mathématique, l’implication est équivalente à l’implication , qu’on appelle sa contraposée. Cela signifie que est vraie dès que est vraie, et inversement.

D’autre part, la proposition signifie: "S’il n’y a pas de face rouge, alors l’autre face ne possède pas de nombre pair".

L’objectif ici est donc de voir quelle(s) sont les carte(s) qui nous permettent de nous prononcer sur la véracité des propositions et .

Procédons donc à une analyse plus approfondie.

Carte n°1: (celle avec un 3)

• si la face au dos est rouge alors cela signifie que est vraie.
• si la face au dos est verte alors cela signifie que est vraie.

Quoiqu’il en soit, en aucun cas nous n’avons pu affirmer quelque chose sur les propositions qui nous intéressent, à savoir ou . La première carte ne sert donc à rien.

Carte n°2: (celle avec un 8)

• si la face au dos est rouge alors cela signifie que est vraie ! Intéressant…
• si la face au dos est verte alors cela signifie que est vraie et, par conséquent, que est fausse.

La carte n°2 nous permet donc, en la retournant de savoir si est vraie ou fausse.

Carte n°3: (la rouge)

• si la face au dos est un nombre pair alors cela signifie que est vraie.
• si la face au dos est un nombre impair alors cela signifie que est vraie et, par conséquent, que est fausse.

Ici aussi, en aucun cas nous n’avons pu affirmer quelque chose sur les propositions ou . Cette carte ne sert à rien non plus ! Si vous l’avez choisie, c’est sans doute que vous confondez la contraposée avec la réciproque . C’est mal. Très mal. Ne me refaites plus jamais ça !

Carte n°4: (la verte)

• si la face au dos est un nombre pair alors cela signifie que est vraie. Par conséquent, cela signifie que est fausse.
• si la face au dos est un nombre impair alors cela signifie que est vraie.

Le fait de retourner cette carte nous permet de savoir si est vraie ou non (ce qui nous permet, par contraposée, de savoir si est vraie ou fausse aussi).

Vous l’aurez compris, les deux cartes à retourner pour tester si l’affirmation est correcte sont la carte avec le 8 et la carte verte. Si vous avez répondu cela, bravo !

En fait, nous voyons que:

a) Si les cartes n°2 et 4 vérifient l’affirmation, alors l’affirmation est vérifiée dans sa globalité;

b) Si la carte n°2 ou la carte n°4 ne vérifient pas l’affirmation, alors l’affirmation est infirmée dans sa globalité.

Il y avait donc une petite difficulté supplémentaire dans ce test, celle de la présence d’un quantificateur universel implicite contenu dans l’expression "Si une carte…." qui devait se lire "Pour toute carte, si …". Et en effet, si juste en retournant la carte 8 on s’aperçoit que l’autre face est verte alors l’affirmation complète est fausse. Mais dans le cas où la face de derrière est rouge, il faut absolument retourner la carte n°4 aussi ! Ceux qui ont répondu "il faut retourner uniquement la carte 8" ont donc à moitié tort et à moitié raison (selon les situations !). Mais en général, ils ont tort. On ne va pas tricher non plus, c’est un test sérieux, voyons.

Parlez-vous le mec bourré ?

Finissons cet article en donnant un deuxième test de (vraie) logique. Cette fois-ci plus concret (pour les amateurs d’éthanol):

« Quatre personnes sont en train de boire dans un bar et vous disposez des informations suivantes : la première boit une boisson alcoolisée, la seconde a moins de 18 ans, la troisième a plus de 18 ans et la dernière boit une boisson sans alcool. Quelle(s) personne(s) devez-vous interroger sur leur âge ou sur le contenu de leur verre pour vous assurer que tous respectent bien la règle suivante : Si une personne boit de l’alcool, elle doit avoir plus de 18 ans. ?»

Bien que ce problème soit logiquement équivalent à celui avec les cartes, les taux de réussite constatés en sont largement supérieurs. Pourquoi ? Vous ne pensez quand même pas que je vais vous pondre une réponse, je vous rappelle que ce blog s’appelle blogdemaths, et pas blogdepsycho…

Pour plus d’informations, vous pouvez consulter les pages Wikipédia française et anglaise sur le sujet (surtout pour l’explication psychologique qui est très intéressante mais bien au-delà de mes pauvres compétences mathématiques…)

Quand les complexes rendent les choses (un peu plus) simples

Cela fait un petit moment que je n’ai pas fait d’article à propos de problèmes géométriques. Je vais donc essayer de réparer cela en vous proposant le petit énoncé suivant (issu du concours Putnam):

Soit (C1) et (C2) deux cercles dont les centres sont séparés de 10 unités, et de rayons respectifs égaux à 1 et 3. Quel est l’ensemble des points M tels qu’il existe un point X appartenant à (C1) et un point Y appartenant à (C2) tels que M est le milieu de [X;Y]  ?

Libre à vous de chercher par vous-même avant de lire la suite de cet article.

Geogebra, à la rescousse

On peut toujours supposer que le centre du cercle (C1) est situé à l’origine du repère et que le cercle (C2) est situé sur l’axe des réels, à 10 unités de l’origine.

A priori, l’ensemble des points M semble un peu mystérieux. Afin d’ébaucher un peu cet ensemble, on peut utiliser la fonction "Trace activée" de Geogebra. Cela signifie que lorsqu’on fait bouger X et Y, le point M (qui bouge lui aussi, évidemment…), laisse une trace rouge en chaque point qu’il traverse.

Voici les superbes gribouillages (dignes d’un très bon élève de CE1) que j’ai réussi à effectuer (on reconnaîtra le style "spirographique"):

Y est immobile. On fait tourner X le long du cercle. M décrit donc un cercle.

Cette fois-ci, c’est X qui est immobile et Y qui tourne. M décrit un nouveau cercle.

Et on fait tourner les serviettes. Enfin, on fait tourner X et Y. Aucun motif particulier ne se dégage pour le moment.

Toujours pas de motif. Donc, on tourne encore !

Serait-ce…. Non.

Mais c’est bien sûr !

L’ensemble cherché semblerait être une couronne centrée en z=5.

Après cette séance d’art, il apparaît donc que l’ensemble des points M cherché est une couronne centrée en 5.

C’est parti pour la preuve

Afin d’analyser et de résoudre ce problème, nous allons nous placer dans le plan complexe. Chaque point M du plan est donc repéré par un nombre complexe z (appelé son affixe). Nous allons prouver que l’ensemble cherché est l’ensemble des points M d’affixe z tels que .

Tout d’abord, le cercle (C1) est l’ensemble des points X dont les affixes sont des nombres complexes de la forme ().

Le cercle (C2), lui, est constitué des points Y dont les affixes sont nombres complexes de la forme ().

Soit M un point du plan qui est le milieu de deux points X et Y appartenant respectivement à (C1) et (C2). Montrons que M appartient à la couronne. Si on note l’affixe de M, cela signifie qu’il existe deux nombres réels tels que

Tout cela est très bien… Mais à quoi cela nous avance-t-il ? Je ne sais pas encore. Voyons voir si nous pouvons modifier l’expression de z afin de mettre ce nombre sous une forme plus familière. Nous pouvons déjà séparer les exponentielles du reste:

On voit déjà apparaître le 5 que nous avions aperçu dans notre conjecture sur la couronne. A présent, utilisons les inégalités triangulaires:

D’où:

Le point M appartient donc bien à la couronne.

Réciproquement, montrons que tout point M de la couronne est le milieu de deux points X et Y appartenant respectivement à (C1) et (C2). Puisque M appartient à la couronne, son affixe z s’écrit où est un réel, et est un réel compris entre 1 et 2 (inclus). Nous cherchons à résoudre l’équation à deux inconnues et suivante:

En fait, on cherche moins que cela. On ne cherche pas à savoir quelles sont les solutions de cette équation mais à savoir si et existent.

Avant cela, revenons à notre dessin. Quand on fixe Y et qu’on fait tourner X (c’est-à-dire quand on fixe et qu’on fait varier ), voici ce qu’on obtient:

Quand Y est immobile, l’ensemble des milieux M’ du segment [XY] est un cercle (Vous le voyez ? C’est le petit cercle, pris en sandwich dans la couronne).

Fixons et voyons ce qui se passe quand se balade dans . Puisque l’affixe du milieu M’ du segment [XY] est , l’ensemble décrit par M’ est l’ensemble:

.

Il s’agit d’un cercle de centre le point d’affixe et de rayon . Sur la figure ci-dessus, c’est le petit cercle coincé dans la couronne. L’idée est donc de choisir (indépendamment de ) de telle sorte que le cercle inscrit dans la couronne touche le point M. Il suffira ensuite de faire tourner M’ sur ce cercle pour que M coïncide avec M’.

L’idée est de choisir Y de telle sorte que l’ensemble décrit par le milieu de [XY] quand X varie (et Y est fixe) soit un cercle sur lequel se situe le point M.

Mathématisons tout cela. La question à laquelle nous tentons de répondre à présent est donc: existe-t-il tel que appartienne au cercle ? Géométriquement, c’est évident. Mais pour être rigoureux, résolvons une équation…

Mais souvenons-nous que . Une rapide étude de fonction nous montre que la quantité est comprise entre 0 et 1 quand est compris entre 1 et 2. Ainsi, cette quantité peut s’écrire comme le cosinus d’un réel . On en déduit donc que le point M appartient au cercle si, et seulement si, donc si, et seulement si, ou .

Bref, peu importe la valeur exacte de (qui dépend de ), nous avons prouvé qu’il existe un (et même deux) tel que le point M soit sur le cercle . En termes géométriques, cela veut dire qu’il existe un point Y tel que M appartient au cercle décrit par le milieu M’ de [XY] quand X parcourt son cercle. Le point Y étant fixé, puisque M est sur ce cercle et que le point M’ décrit ce cercle quand X varie, il existe donc un point X pour lequel M’=M.

Nous avons donc prouvé (non sans peine !) que si M est un point de la couronne, alors il existe deux points X et Y tels que M est le milieu de [XY]. Tout ça pour ça… faire des mathématiques peut être un peu ingrat parfois !

Un critère visuel de divisibilité par 7

Nous avons (presque) tous appris à l’école Primaire ou au Collège à savoir si un nombre entier donné est divisible par 2, 3, 4, 5, 6 ou 10. Parfois même, pour les plus chanceux d’entre nous, on nous a appris à reconnaître les nombres qui sont divisibles par 8. Mais s’il y a bien un critère qu’on se garde bien de nous expliquer, c’est celui de la divisibilité par 7.

Est-il vraiment si difficile à faire apprendre ou comprendre aux élèves ? Nous allons tenter de décrire un critère plutôt simple dans cet article. D’ici la fin, vous devriez être capables de dire si 198749502 est divisible par 7 sans avoir fait aucun calcul.

Le critère de divisibilité par 7 que je vais décrire a été posté sans véritable explication par un certain David Wilson sur ce blog. J’avoue ne pas savoir s’il en est l’auteur initial ou si cela est connu depuis bien plus longtemps. Peu importe, vous allez voir, c’est à la fois simple et beau !

Un joli graphe orienté

Voici le très esthétique et mystérieux graphe que nous allons utiliser pour savoir si un nombre est divisible par 7. (Il s’agit d’une reproduction du graphe donné dans le lien sus-mentionné réalisée à l’aide de Tikz).

Comme vous le voyez, il y a deux types de flèches sur ce graphe: les flèches noires et les flèches bleues. Chaque type de flèche va être utilisé à tour de rôle.

Avant de donner le mécanisme de fonctionnement général, nous allons donner un exemple afin d’illustrer la démarche.

Principe général

Pour savoir si un nombre est divisible par 7, on effectue les étapes suivantes:

• Partir du noeud 0
• Parcourir autant de flèches noires que le chiffre de gauche de
• Parcourir une flèche bleue
• Parcourir autant de flèches noires que le chiffre suivant
• Parcourir une flèche bleue
• etc.
• Parcourir autant de flèches noires que le dernier chiffre de
• Si le nœud d’arrivée est 0 alors est divisible par 7, sinon il ne l’est pas.

En gros, on parcourt autant de flèches noires que chaque chiffre, et on parcourt une flèche bleue chaque fois qu’on change de chiffre. Facile, non ?

Remarque: si à un moment on tombe sur le noeud 0, vu qu’il n’y a pas de flèche bleue partant de ce noeud, on passe directement au chiffre suivant.

Mais pourquoi ça marche ?

J’avoue que la première fois que j’ai vu ce critère, j’étais assez étonné par le caractère quasiment magique de cette recette. Il m’a fallu un bon petit moment avant de comprendre les raisons qui font que cela marche (je suis long à la détente parfois).

Tout se passe modulo 7, comme on pouvait s’y attendre.

Les flèches noires – Leur fonction est très simple. Chaque flèche noire représente l’addition de 1 modulo 7. Par exemple, quand on part du noeud 3 et qu’on parcourt 6 flèches noires, cela correspond à effectuer l’opération . Comme le résultat de cette opération est , on arrive bien au noeud 2.

Les flèches bleues – Pour comprendre leur utilité, partons du noeud 1 et parcourons toutes les flèches bleues. Le cycle obtenu est le suivant: 1, 3, 2, 6, 4, 5, 1.  Si on observe bien, cela correspond aux différents restes des puissances de 10 modulo 7:

Ainsi, parcourir une flèche bleue revient à multiplier le numéro du noeud sur lequel on se situe par 10 modulo 7.

Résumons:

• une flèche noire = .
• une flèche bleue = .

Cela est bien beau mais ne nous explique pas pourquoi on commence par le chiffre le plus à gauche de , ni pourquoi on parcourt une flèche bleue à chaque changement de chiffre.

Pour tenter d’expliquer cela, reprenons notre exemple . L’astuce consiste à écrire

et à utiliser les propriétés de compatibilité de l’addition et de la multiplication modulo 7. Ainsi, on commence par calculer 3 modulo 7 (parcours de trois flèches noires) puis à multiplier par 10 modulo 7 (parcours d’une flèche bleue), puis à ajouter 4 modulo 7 (parcours de 4 flèches noires, puis à multiplie par 10 modulo 7 (parcours d’une flèche bleue), et enfin à ajouter 9 modulo 7 (parcours de neuf flèches noires).

Ce graphe nous donne donc plus que la divisibilité par 7 car le résultat final est le reste modulo 7 de . Si on arrive sur le noeud 0, c’est que et donc que est divisible par 7. Par exemple, le noeud d’arrivée de est 6, donc et n’est donc pas divisible par 7.

Pour le plaisir des yeux, voici dans le fichier pdf suivant une animation qui permet de visualiser que 532 est divisible par 7:

Animation de la divisibilité par 7

Alors, 198749502 est-il divisible par 7 ?

Une généralisation

A moindres frais, nous pouvons sur le même principe avoir des critères de divisibilité par 11, 13, 17 etc. car, comme on l’a vu, il suffit de connaître les différents résultats de la multiplication par 10 modulo 11, 13 ou 17.   Voici les graphes obtenus en faisant joujoux avec Tikz:

Je n’ai pas été au-delà car le nombre de flèches commençait à rendre les graphes assez moches, mais vous avez compris le principe !

Notes:

1) La belle symétrie du graphe pour 11 montre que tout nombre palindrome avec un nombre pair de chiffres est divisible par 11 !

2) Pour les gens intéressés, voici le code Tikz que j’ai écrit pour obtenir ces graphes: http://pastebin.com/nisvHkxQ

Un tour de magie mathématique…

Ce que je vais vous apprendre dans cet article va changer votre vie. Vous allez passer de simple inconnu banal à star mondiale de la magie. Vous allez faire passer David Copperfield pour un amateur.

Aller, trêve de publicité mensongère et d’accroche gratuitement racoleuse, je vais vous présenter un petit tour de magie mathématique bien sympathique. La seule chose dont vous aurez besoin, ce sont les 10 cartes suivantes (que j’ai confectionnées moi-même… elles sont pas trop PIMP mes cartes "blogdemaths" ?):

Pour une version imprimable (en pdf), cliquez ici: Cartes magiques. Pour information, ces cartes ont été réalisées (par mes soins) en LaTeX et plus précisément à l’aide du (génialissime) package Tikz.

Mise en œuvre 

Voici comment se déroule le tour:

1. Demandez à un spectateur de choisir un nombre au hasard entre 1 et 100 et de l’inscrire sur une feuille de papier  à l’abri des regards indiscrets.
2. Montrez-lui tour à tour chacune des 10 cartes ci-dessus, et demandez-lui à chaque fois si le nombre qu’il a choisi est inscrit sur la carte.
3. Faites semblant de réfléchir/de regarder dans votre boule de cristal/d’invoquer l’esprit de l’accordéon Yvette Horner… Bref, faites votre magicien.
4. Annoncez-lui le nombre qu’il avait choisi au départ. Demandez-lui de retourner le papier pour confirmer que c’était bien le nombre qu’il avait choisi.
5. Récoltez les fruits de votre nouvelle célébrité.

(Remarque: Le fait d’écrire le nombre sur un papier n’est pas nécessaire mais il y a toujours des enf…. des plaisantins qui changeront de nombre à la fin et diront que ce n’est pas le nombre qu’ils avaient choisi juste pour nous prouver que notre tour ne marche pas… mais on ne blague pas avec les mathématiques. ON NE BLAGUE PAS AVEC LES MATHÉMATIQUES.)

Mais comment marche ce tour ? On est sur blogdemaths, donc vous vous doutez bien qu’il n’y a pas de sorcellerie derrière tout cela, mais seulement des mathématiques.

Un petit exemple…

Imaginons que vous soyez le spectateur et que vous choisissiez le nombre 32. Voyons toutes les cartes qui contiennent le 32:

Voici les 3 seules cartes du jeu qui contiennent le numéro 32

Maintenant, je vous laisse essayer de deviner comment on peut trouver le nombre 32 à partir de ces cartes.

Vous avez trouvé ? Il suffit d’additionner les nombres les plus en haut à gauche.

3+8+21 = 32. Le compte est bon.

Ainsi, chaque fois que la personne vous dit que le nombre qu’elle a choisi est inscrit sur une carte, vous additionnez le nombre qui apparaît en haut à gauche de cette carte. Le total de tous ces nombres vous donnera le nombre choisi par le spectateur.

On ne peut pas faire de tour plus simple à exécuter ! (A condition bien entendu de savoir additionner mentalement quelques nombres…) Et très franchement, très peu de gens s’apercevront qu’on n’a fait qu’une simple somme.

Explication mathématique du tour

L’explication, même si elle est simple a posteriori, est loin d’être évidente et requiert l’utilisation d’un théorème que nous avons déjà démontré dans ce blog: le théorème de Zeckendorf. Rappelons ce que nous dit ce théorème:

Tout entier naturel non nul s’écrit de manière unique comme la somme de nombres de Fibonacci non consécutifs.

Si vous remarquez bien, le premier nombre de chaque carte est un nombre de Fibonacci. Rappelons que la suite de Fibonacci est la suivante: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Et tout nombre inférieur à 100 peut s’écrire comme une somme de ces nombres, et ce, de manière unique.

Ainsi, chaque nombre entier compris entre 1 et 100 n’apparaît que sur une unique combinaison de cartes. Par exemple, le nombre 32 est l’unique nombre à apparaître à la fois sur les cartes commençant par 3, 8 et 21 et à n’apparaître sur aucune autre carte. On ne peut pas se tromper !

Comment a-t-on réalisé ces cartes ? Très simplement, en commençant par prendre 10 cartes vierges, et en écrivant 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 sur chacune d’entre elle. Puis, pour tout entier inférieur à 100, on a effectué sa décomposition de Zeckendorf, et on a inscrit ce nombre sur chacune des cartes correspondant. Par exemple, puisque la décomposition de 32 est 32=3+8+21, on a écrit le nombre 32 sur les trois cartes comportant le 3, le 8 et le 21.

Comment rendre le tour encore plus spectaculaire ?

Afin de renforcer l’impact émotionnel de ce tour vous pouvez:

• Présenter les cartes dans un ordre différent que celui qui consiste à montrer d’abord la carte commençant par le 1, puis la carte commençant par le 2, etc.
• Dire que ces cartes comportent chacune des nombres choisis aléatoirement entre 1 et 100 (on sait que cela est faux, mais ce petit mensonge renforcera l’effet du tour). De toute façon, rare sont les personnes qui connaissent la suite de Fibonacci, et encore plus rares sont les gens qui s’apercevront que les nombres inscrits sur ces cartes suivent un schéma "régulier" (si tant est que la décomposition de Zeckendorf soit quelque chose qu’on puisse qualifier de régulier). Personnellement, je pense que la force de ce tour est ici.
• Faire croire que la couleur de chaque carte joue un rôle (c’est vicieux ça !) dans le fait de trouver le nombre.
• Faire croire que vous êtes le fils spirituel de Madame Soleil (risqué).

J’espère que ce tour vous a plu, moi je retourne auprès de Claudia Schiffer…

Sources:  Fibonacci Magic Cards Brother Alfred Brousseau, Fibonacci Quarterly 10 (Janvier 1972)

Et pour une vidéo (en Anglais) expliquant le même tour, mais cette fois en utilisant la décomposition en base 2 d’un nombre (qui est unique, elle aussi !), vous pouvez regarder ceci.

2013, un quart de siècle après…

Une nouvelle année commence… voilà donc pour moi l’occasion d’écrire un nouvel article. J’avais, en 2011, écrit un article recensant certaines particularités du nombre 2011. Manquant cruellement d’originalité, je me suis dit que j’allais faire la même chose en 2013 et que mes lecteurs n’y verront que du feu. Malheureusement, le nombre 2013 est particulièrement inintéressant. Pour dire, sur une échelle d’ennui de 1 à 10, le nombre 2013 aurait la note de "Dictionnaire des roches et des minéraux en cinq volumes". Pour voir quelques (maigres) propriétés du nombre 2013, voir ce lien.

Cependant, 2013 a une particularité qui a retenu mon attention. C’est la première année depuis 1987 où aucun chiffre ne se répète. N’est-ce pas étonnant ? On vient de vivre vingt-cinq années consécutives qui contiennent au moins deux fois le même chiffre (1988, 1989, …, 2011, 2012). Il fallait bien que cela cesse.

Dans cet article, nous allons porter notre attention sur les nombres qui ne contiennent pas deux fois le même chiffre (comme 42, 103, 2049, 38295…). Y en a-t-il beaucoup ? Une infinité ? Un nombre fini ? S’il y en a un nombre fini, quel est le plus grand ? Le plus petit ?

Tous les nombres considérés dans cet article seront écrits en base dix (car il me semble que c’est celle qu’on utilise pour écrire les années. A vérifier.)

Faisons les fonds de tiroirs…

Faisons un bond dans le temps et allons en l’an 10 000 000 000 ap. J.-C. A cet époque, les gens seront tristes. Tristes parce qu’il sauront que plus aucune année n’aura la même particularité que 2013. Toutes les années alors auront au moins un chiffre qui se répète.

Plus précisément, tout nombre à 11 chiffres (ou plus) possède au moins deux chiffres qui se répètent. Et cela, c’est de la faute du principe des tiroirs (encore appelé principe des cases à pigeons par nos amis anglo-saxons) que nous allons tenter d’expliquer ici.

Si vous possédez 4 chaussettes et que vous les disposez dans 3 tiroirs alors il y aura au moins un tiroir qui contiendra au moins deux chaussettes. Vous pouvez essayer chez vous, ça marche ! De même, si vous possédez 11 chaussettes et que vous les disposez dans 10 tiroirs alors il y aura un tiroir qui contiendra au moins deux chaussettes. Maintenant, imaginez que ces 11 chaussettes sont les 11 places de votre nombre à 11 chiffres (il y a la place du chiffres des unités, la place du chiffre des dizaines, etc.) et que les 10 tiroirs sont les chiffres de 0 à 9. Et bien il y aura deux emplacements (chaussettes) qui auront un même chiffre (tiroir) en commun.

Si cela ne vous convainc pas, essayez par vous même, écrivez un nombre à 11 chiffres sans utiliser deux fois le même chiffre. Puis cognez-vous la tête contre le mur suffisamment fort pour comprendre que ça n’est pas possible.

En clair, il n’y a qu’un nombre fini de nombres dont tous les chiffres sont différents. Et tout nombre de ce type aura donc 10 chiffres ou moins.

Dénombrons-les tous !

On a donc vu qu’il n’y a qu’un nombre fini de nombres qui ne possèdent aucun chiffre qui se répète. Mais combien y en a-t-il en tout ? Afin de les compter, nous allons nous intéresser successivement aux nombres à 1 chiffre, puis aux nombres à 2 chiffres, etc. jusqu’aux nombres à 10 chiffres. On a vu qu’au-délà (11 chiffres), tout nombre a forcément deux chiffres identiques (au moins).

• Un chiffre: Tout nombre a un chiffre vérifie forcément la propriété qu’il n’existe pas deux chiffres identiques. Cela en fait 10 au total.
• Deux chiffres: On considère un nombre a deux chiffres, dont les deux chiffres sont différents. Le premier chiffre (chiffre des dizaines) ne pouvant valoir 0 (sinon ce serait un nombre à un chiffre !), il y a donc 9 possibilités pour le choisir. Une fois le premier nombre fixé entre 0 et 9, il faut choisir le deuxième nombre de telle sorte qu’il soit différent du premier. Par exemple, si le premier chiffre est 3, alors le deuxième chiffre peut être choisi parmi les chiffres 1, 2, 4, 5, 6, 7, 8, 9. Cela fait neuf choix possibles pour le deuxième nombre une fois le premier chiffre fixé. Au total, il y a donc nombres à deux chiffres, dont les chiffres sont différents.
• Trois chiffres: Vous avez sans doute saisi le principe. On choisit le premier chiffre (chiffre des centaines) parmi 0, 1, 2, …, 9 ce qui donne neuf choix. Pour chacun de ces choix, on choisit le deuxième chiffre (chiffre des dizaines) parmi neuf chiffres restants. Enfin, on choisit le troisième chiffre en évitant de prendre le même chiffre que les deux premier chiffres choisis, ce qui laisse huit choix. Au total, le nombre de nombres à trois chiffres dont tous les chiffres sont différents est .
• Quatre chiffres: Le raisonnement est le même. Il y en a .
• etc.

Finalement, le nombre d’entiers naturels dont l’écriture en base 10 ne contient aucun chiffre qui se répète est

ce qui donne . Il y a donc exactement 8 877 681 nombres qui n’ont aucun chiffre qui se répète dans leur écriture en base 10. Je sais pas vous, mais moi, ça m’en bouche un coin.

Pour l’anecdote, le plus petit de ces nombres est 0 (évidemment) et le plus grand est 9 876 543 210 (qui possède dix chiffres). L’année 9 876 543 211 sera donc une année noire. L’année de la fin des années sans deux fois le même chiffre !

Bonne année 2013 à tous !

Et si le Père Noël se trompait ?

La vie de Père Noël n’est pas une sinécure. En plus d’avoir à apporter des cadeaux à des millions d’enfants avec des contraintes temporelles et physiques quasiment impossibles à remplir, il doit faire face à une angoisse terrible chaque année: apporter le bon cadeau au bon enfant. Signalons que le fait qu’il boive une bouteille de vodka avant chaque tournée pour se donner du courage (et se réchauffer) n’arrange en rien ce problème.

Et si le Père Noël se trompait complètement cette année ? Et s’il rendait tous les enfants de la Terre malheureux (sans exception) ? Plus précisément, la question à laquelle nous allons répondre dans cet article est la suivante: quelle est la probabilité qu’aucun enfant ne reçoive, le 25 Décembre au matin, le cadeau qui lui était destiné ? (ce qui serait tout de même une sacrée coïncidence…)

Mise en place du problème

Dans la suite de cet article, nous noterons par le nombre d’enfants que le Père Noël va voir cette année. On suppose qu’on a numéroté tous ces enfants de à une bonne fois pour toute. De même, on numérote de à tous les cadeaux (ou lots de cadeaux car certains enfants en reçoivent plusieurs !) de telle sorte que le cadeau numéro appartienne à l’enfant numéro .

Nous représenterons à l’aide de la notation la tournée du Père Noël le 24 Décembre au soir de la façon suivante:

est le numéro du cadeau que le Papa Noël a déposé chez l’enfant numéro

Ainsi, si le Père Noël apporte le bon cadeau à l’enfant alors . Et le Père Noël se trompera complètement cette année si pour tout nombre entier compris entre et , .

Afin de calculer la probabilité qui nous intéresse dans cet article, à savoir la probabilité qu’aucun enfant ne reçoive le cadeau qui lui est destiné, on fait l’hypothèse que toutes les tournées ont la même probabilité d’apparaître (même si la présence d’alcool dans le sang de ce monsieur tout rouge peut quand même nous faire sérieusement douter de la validité de cette hypothèse). Ainsi, il nous faut donc trouver le nombre de tournées pour lesquelles pour tout .

Sachant qu’il y a tournées possibles au total (chaque tournée est, comme vous l’avez peut-être déviné, une permutation de l’ensemble ), la probabilité cherchée vaudra

Mais avant de nous lancer tout de suite dans le cas général de enfants, voyons ce qu’il se passe dans le cas d’un petit nombre d’enfants, pour mieux comprendre.

Cas d’un enfant (n=1)

Cette année, tous les enfants de la Terre ont été particulièrement peu sages. Seul un enfant a su se tenir correctement. La tournée du Père Noël n’en sera que plus facile me direz-vous.

Puisqu’il n’y a qu’un enfant (et donc qu’un seul cadeau à livrer), il n’y a aucune chance pour que ce petit enfant reçoive un cadeau qui n’est pas le sien. La probabilité  cherchée est donc .

Cas de deux enfants

Dans le cas où il n’y a que deux enfants à livrer (et donc qu’il n’y a que deux cadeaux à apporter), la seule façon de se tromper est d’apporter le cadeau n°2 à l’enfant 1 et le cadeau n°1 à l’enfant 2. Il n’y a donc qu’une seule façon de se tromper totalement, et la probabilité cherchée est donc .

Cas de trois enfants (non, je vous rassure, on ne va pas tous les faire comme ça…)

Introduisons une notation. Pour représenter la tournée dans laquelle l’enfant 1 reçoit le cadeau de l’enfant 2, l’enfant 2 reçoit le cadeau de l’enfant 3 et l’enfant 3 reçoit le cadeau de l’enfant 1, nous écrirons:

Dans la ligne du haut, sont écrits les numéros des enfants. Le numéro correspondant dans la ligne juste en dessous est le numéro du cadeau reçu par cet enfant.

Vous pouvez vérifier rapidement que les seules tournées pour lesquelles aucun enfant ne reçoit son cadeau sont

et

ce qui donne deux possibilités. La probabilité cherchée est donc .

Le cas général

On se place à présent dans le cas où le Père Noël va rendre visite à enfants (avec ). Nous allons trouver le nombre de tournées où aucun enfant ne reçoit son cadeau en faisant la disjonction des cas suivante:

• Soit l’enfant 1 reçoit le cadeau de l’enfant 2;
• Soit l’enfant 1 reçoit le cadeau de l’enfant 3;
• etc.
• Soit l’enfant 1 reçoit le cadeau de l’enfant .

Cela donne cas à étudier (l’étude de chaque cas est similaire).

1. Cas où l’enfant 1 reçoit le cadeau de l’enfant 2.
   Nous allons distinguer deux sous-cas disjoints:

   a) Soit alors l’enfant 2 reçoit le cadeau de l’enfant 1. Ainsi, les enfants 1 et 2 ont vus leurs cadeaux échangés par le Père Noël. Autrement dit, la tournée est de la forme:
   
   On remarque donc que les cadeaux 3, 4, …, vont être distribués parmi les enfants 3, 4, …, . Il suffit donc de compter combien de tournées avec les enfants 3, 4, …, incluant les cadeaux 3, 4, …, sont telles qu’aucun enfant ne reçoive le bon cadeau. Par définition, ce nombre est .

   b) Soit l’enfant 2 ne reçoit pas le cadeau de l’enfant 1 (). Ainsi, les tournées cherchées sont de la forme:
   
   Si on renomme les enfants 2, 3, 4, …, en 2′, 3′, 4′, …, , et si on renomme les cadeaux 1, 3, 4, …, en 2′, 3′, 4′, …, , alors le nombre de tournées cherché est le même que le nombre de tournées pour lesquelles on distribue aux enfants 2′, 3′, …, les cadeaux 2′, 3′, …, sans qu’aucun enfant n’obtienne le cadeau qui lui correspond. Par définition, ce nombre vaut .

   Par suite (a) + b)), le nombre de tournées pour lesquelles l’enfant 1 reçoit le cadeau de l’enfant 2 et pour lesquelles aucun enfant ne reçoit son cadeau est .

2. De la même manière, on montre que le nombre de tournées dans lesquelles l’enfant 1 reçoit le cadeau de l’enfant et où aucun enfant ne reçoit le bon cadeau est .
3. Au final, le nombre de tournées pour lesquelles aucun enfant ne reçoit son cadeau attitré est . D’où:

Calcul explicite de la suite

Nous venons de trouver une relation de récurrence vérifiée par le suite . Nous allons nous en servir pour exprimer explicitement la suite qui n’est rien d’autre que la probabilité qu’on recherche. Commençons par remarquer que la relation précédente donne:

Si est la suite définie par , on a donc

Comme ( et ont été calculés dans les paragraphes ci-dessus),  on en déduit que

c’est-à-dire

En divisant la relation ci-dessus par , on obtient

d’où

En sommant les deux membres de 3 à n, on reconnaît une somme télescopique, ce qui donne au final:

Donc,

Comme , on a donc

Ouf !

Bon alors, combien de chances a le Père Noël de se planter lamentablement ?

Revenons au problème qui nous occupe. Comme nous venons de le voir, la probabilité qu’aucun enfant ne reçoive le bon cadeau est

Voici un tableau dans lequel on a calculé une valeur approchée de cette probabilité pour quelques valeurs de :

(J’ai calculé ces valeurs à l’aide d’un programme écrit avec Algobox. Mais au-delà de , le programme plantait, la factorielle devenait trop grande…)

Question: peut-on préciser cette probabilité dans le cas où est bien plus grand ? Car il n’y a pas que 100 enfants sur cette planète….

Vers quoi tend cette probabilité ?

Tout d’abord, remarquons que . Ensuite, étalons un peu notre science en disant que n’est rien d’autre que le nombre . Notre probabilité tend donc, quand est grand, vers

Avec encore plus de connaissances sur les séries alternées, on peut affirmer que, s’il y a enfants, la différence est inférieure à . Ainsi, la probabilité que le Père Noël se trompe entièrement dans ses cadeaux sera égale à 0.3678794411 (à près) dès que est plus grand que c’est-à-dire dès que est plus grand que 13.

A fortiori, dans le cas où est de l’ordre de plusieurs millions, est plus grand que 13 (oui !) et la probabilité qu’aucun enfant ne reçoive le cadeau qui est le sien est de 0.3678794411 à près.

En résumé…

La probabilité que le Père Noël se trompe entièrement est proche de 36% lorsque le nombre d’enfants à visiter est de l’ordre de plusieurs millions.

Autrement dit, et c’est un fait étonnant (voire contre-intuitif), chaque année, le Père Noël a plus d’une chance sur trois de ne distribuer le bon cadeau à aucun enfant ! C’est donc une belle performance que presque tous les enfants reçoivent leur cadeau attitré sous le sapin chaque 25 Décembre.

Bravo petit Papa Noël ! (et n’oublie surtout pas de m’apporter ma console de jeux cette année…)

 

(N.B: le nombre de cet article s’appelle le nombre de dérangements ou encore sous-factorielle, et il s’agit du nombre de permutations sans points fixes).