Dans la vie de tous les jours, il n’est pas rare de nous trouver dans des situations où il faut prendre des décisions. C’est le principe même de la liberté à laquelle nous sommes si attachés... Les maths peuvent-elles nous aider ? Je voudrais donner quelques exemples concrets où des maths, pas toujours faciles, peuvent effectivement nous aider (un peu). Commençons par quelques problèmes présentés sous forme d’amusettes.

Des problèmes ?

• Le problème des secrétaires

La directrice des relations humaines d’une entreprise veut embaucher un secrétaire. Une centaine de candidats se présentent tour à tour pour une audition. Après chaque audition, la directrice est capable de comparer le candidat qu’elle vient de voir avec les précédents, mais elle doit se décider tout de suite. Si elle n’embauche pas sur-le-champ un candidat, elle ne pourra pas le rappeler plus tard et elle passe au suivant. Bien sûr, les candidats se présentent dans un ordre aléatoire et il est impossible a priori de prévoir quand se présentera le meilleur. Quels conseils donner à la directrice ? Comment faire pour optimiser la chance de recruter le meilleur candidat ?

Pour l’instant, pensez à cette question comme un jeu, même si je vous entends déjà protester que les hypothèses ne sont pas raisonnables... Vous pourriez
dire que la directrice peut non seulement comparer mais qu’elle peut probablement aussi « mesurer les valeurs intrinsèques des candidats » et qu’elle a peut-être une idée a priori de ce qu’on peut attendre d’un secrétaire exceptionnel. Vous pourriez dire aussi qu’il est bien rare qu’une directrice ne puisse pas rappeler un candidat qu’elle a vu la semaine qui précède (le fameux « on vous écrira »...) Ou bien que la phrase « tel candidat est meilleur que tel autre » n’a pas grand sens. Ou encore que le but n’est peut-être pas de recruter le meilleur et qu’on serait peut-être aussi satisfait si on recrutait le second ou même le troisième, car de la façon dont le problème est posé, il revient au même de recruter le second ou le dernier et on ne cherche vraiment que le meilleur : pas très raisonnable. Ou encore que ces auditions coûtent du temps et de l’argent et que la directrice a peut-être simplement le souhait de recruter rapidement quelqu’un qui fait l’affaire. Etc.

Une parenthèse sur le sexisme des mathématiciens. L’énoncé de ce problème date des années 1960. On en trouve plusieurs versions mais il est clair que le décideur est toujours un homme et que les secrétaires sont toujours des femmes... Une version très populaire s’appelle le problème du mariage : un homme fait défiler des « candidates au mariage » et ... il fait son choix. On raconte même que le grand astronome Kepler aurait abordé le problème de son second mariage de cette manière. Tout cela était il y a longtemps et on pourrait presque oublier ces clichés. Mais on trouve aujourd’hui sur internet des descriptions du problème sous l’appellation « concours de beauté » ou encore pire « Optimisez votre femme ! ». Le sexisme des mathématiciens est-il en voie de disparition ? J’aimerais pouvoir l’affirmer.

• Acheter un appartement et autres problèmes du même genre

Vous voulez acheter un appartement. Tous les jours vous vous connectez sur un site de vente d’immobilier, vous entrez vos critères de recherche, et vous voyez quelques offres. Parfois aucune, parfois une, parfois deux, plus rarement trois. Le problème est que vous avez une date limite : il est impératif que vous ayez acheté dans six mois ! Pour chaque annonce, vous allez visiter et il vous faut décider tout de suite. Demain ce sera trop tard pour celle-ci mais demain peut-être vous trouverez mieux ? Quelle stratégie employer pour avoir la meilleure chance de trouver le meilleur appartement ?

J’entends les mêmes protestations : après-tout, trouver le deuxième appartement pourrait aussi être acceptable... C’est un peu le même problème que le précédent à ceci près qu’on ne sait pas a priori le nombre d’appartements qui vont se présenter dans les six mois.

Mais vous pourriez tout aussi bien vous trouver sur une autoroute avec un réservoir d’essence qui vous permet de rouler encore 200 km et vous voyez passer quelques stations service qui vous proposent des prix qui vous semblent prohibitifs. La suivante, peut-être, sera meilleur marché ? Oui, mais si elle ne l’est pas ? Et si je suis obligé de faire le plein lorsque le réservoir est vide et que la station est la plus chère de France ?

• Le problème de la place de parking

Vous roulez en voiture en direction d’un endroit précis où vous voulez aller, un cinéma par exemple. Sur le bord de la route, il y a des places de stationnement. Certaines sont libres et d’autres sont occupées. Vous constatez une proportion de remplissage des places, par exemple de 95%. Faut-il se garer dès que possible ou bien est-il préférable de continuer, au risque de ne rien trouver et de devoir dépasser le cinéma, et trouver une place encore au delà ? Quelle stratégie employer pour espérer marcher le moins possible depuis le parking jusqu’au cinéma ?

Remarquez que votre ambition est un peu plus raisonnable que dans le cas précédent : vous ne cherchez pas à tout prix à optimiser votre chance de trouver la place la plus proche du cinéma mais plutôt à minimiser l’espérance de la distance que vous allez devoir faire à pieds.

Mais on pourrait faire d’autres critiques : peut-être que vous n’êtes pas le seul à aller au cinéma et que les places libres sont plus rares à mesure qu’on s’approche du cinéma ?

• Les problèmes de Cayley et Moser

En 1875, le célèbre mathématicien anglais Arthur Cayley pose le problème suivant. Supposons qu’on mette sur la table cent enveloppes fermées qui contiennent des chèques de 1, 2, 3, etc. jusque 100 euros (ou plutôt livres sterling ou peut-être même des guinées puisque c’était en Angleterre au dix-neuvième siècle). Les enveloppes sont mélangées. Vous ouvrez une enveloppe, puis une seconde, puis une troisième etc. A chaque instant, vous avez le droit de choisir entre deux options : soit vous empochez le chèque que vous venez de choisir et le jeu s’arrête, soit vous déchirez ce chèque et vous piochez à nouveau dans ce qui reste. Disons que vous avez le droit de tirer dix enveloppes par exemple. Le problème est de déterminer la meilleure stratégie, c’est-à-dire celle qui vous permet d’espérer gagner le plus possible.

En 1956, Moser a formulé une autre version de ce problème. Chaque minute, une machine tire au hasard devant vous un nombre compris entre 0 et 1. Le hasard est supposé uniforme ce qui veut dire qu’il y a par exemple une chance sur dix que ce nombre soit compris entre 0,2 et 0,3 puisque l’intervalle entre 0,2 et 0,3 couvre un dixième de l’intervalle allant de 0 à 1. Vous pouvez observer cette machine pendant 100 minutes par exemple. Chaque minute, vous avez le droit de dire « Stop » et on vous remet la somme indiquée par le nombre, par exemple en millions d’euros : si vous arrêtez quand la machine montre 0,752 vous avez gagné 752 000 euros ;-) Mais s’il vous reste encore 20 minutes par exemple, et donc encore 20 tentatives, vous auriez peut-être intérêt à attendre encore un peu, parce que d’ici là ce serait bien étonnant que vous ne trouviez pas mieux ?

Bien sûr, cela semble artificiel, mais n’avons-nous pas tous vécu des situations de choix analogues à celle-ci, où nous hésitons entre prendre ce qu’on a et tenter sa chance à nouveau (peut-être pas pour des millions d’euros [1]) ?

Inutile de donner d’autres exemples. Vous aurez compris que les problèmes dont nous discutons ici sont tous du même type : au fil du temps, des événements se produisent, souvent de manière aléatoire ; nous gagnons de l’information progressivement, et puis à certains moments nous devons prendre une décision. Le but consiste à mettre au point une stratégie qui optimise notre chance de gagner, ou tout au moins d’avoir un résultat satisfaisant. Vous aurez compris également que les problèmes formulés ci-dessus ont souvent des hypothèses « naïves » et on peut se demander s’ils ont vraiment à voir avec la réalité. Souvent, les mathématiques simplifient les vrais problèmes à l’extrême, parfois trop... Mais parfois le fait de cerner les difficultés permet de mieux comprendre, tout simplement.

Des solutions ?

Voici donc les solutions des problèmes ci-dessus :

• Le problème des secrétaires

La meilleure stratégie est celle des 37%. En clair, cela signifie que la directrice doit d’abord auditionner 37% des candidats sans prendre aucune décision. Ensuite commence la période de décision : la première fois que la directrice voit un candidat qui est meilleur que tous ceux qui l’ont précédé, il faut qu’elle l’engage.

Voilà un énoncé qui peut surprendre ? Il semble que spontanément, nous avons tendance à prendre des décisions trop tôt.

En fait, la « vraie » solution du problème est un peu plus précise. Pour chaque nombre $n$ de candidats, il existe un autre nombre $f(n)$ (qu’on peut calculer explicitement avec une calculette si on le souhaite) et qui est tel que la meilleure stratégie consiste en une période d’observation pendant les $f(n)$ premières auditions, suivie ensuite par une période de décision pendant laquelle on prend le premier candidat qui se présente et qui est meilleur que tous les précédents. A titre d’exemple, voici quelques valeurs :

\[ f(3)=2 \quad ; \quad f(4)=2 \quad ; \quad f(5)=3 \quad ; \quad f(10)=4 \quad ; \quad ... \quad ; \quad f(40)=16 \quad ; \quad ... \quad ; \quad f(1000)=369 \quad ... \]

S’il y a 40 candidats par exemple, il est bon de ne rien décider avant d’avoir vu les 16 premiers. Nous verrons plus loin comment calculer ce nombre $f(n)$ mais il se trouve que si $n$ est assez grand, il est presque égal à $0,37 n$, d’où les 37%.

• Le problème de la place de parking

Ici encore la meilleure stratégie consiste à ne rien faire jusqu’à une certaine distance $D$ du but, puis de prendre la première place disponible qu’on rencontre. Certes ! mais quel est ce $D$ ? Supposons que la proportion de places occupées soit supérieure à 50%, comme c’est le cas de notre exemple 95%, c’est-à-dire 0,95. Alors, on cherche la plus petite puissance de cette proportion qui soit inférieure à 0,5. En l’occurrence c’est 14 car $0,95^{14}\lt 0,5\lt 0,95^{13}$. Alors, $D=14$, c’est-à-dire que c’est à partir de 14 places de parkings avant le cinéma qu’il faut commencer à chercher une place.

• Les problèmes de Cayley et Moser

Voici la solution du problème de Moser. On définit une suite de nombres :

\[ 0,5 \quad ; \quad 0,625000 \quad ; \quad 0,695312 \quad ; \quad 0,741730 \quad ; \quad 0,775082 \quad ; \quad 0,800376 \quad ; \quad ... \]

Le premier est 0,5 et chacun est obtenu à partir du précédent en appliquant la fonction $(1+x^2)/2$. Par exemple, le suivant dans la liste est $(1+0,800376^2)/2 \simeq 0,820301$. Le centième de la liste est 0,981208. Vérifiez-le [2] !

La meilleure stratégie est alors la suivante. Plus le temps presse, c’est-à-dire moins il vous reste de tentatives, et plus il faut être prudent ! En fait, s’il reste $n$ tentatives, il faut s’arrêter et prendre ce qu’on a si le nombre qui apparaît est supérieur au $n$-ème nombre de notre suite. Pour $n=1$, c’est assez clair : s’il vous reste une chance et si vous avez devant vous un nombre inférieur à 0,5, il vaut mieux tenter sa chance puisqu’en moyenne on peut espérer 0,5 au prochain coup. Mais je ne pense pas qu’il soit évident que la bonne chose à faire s’il reste 5 tentatives soit d’arrêter le jeu si on a devant soi une offre supérieure à 0,775082. Voilà un exemple d’une stratégie à laquelle on n’aurait pas pu penser sans faire un peu de maths !

Des solutions ... utiles en pratique ?

Nous l’avons dit : chacun de ces problèmes suppose un certain nombre d’hypothèses... contestables ! Depuis les années 1960, on assiste à une floraison de travaux qui étudient des problèmes similaires, dans lesquels on ne fait plus telle ou telle hypothèse. Par exemple, on pourrait supposer que la directrice qui recrute a effectivement la possibilité de rappeler celui qu’elle a auditionné la veille, mais que ce dernier peut très bien ne plus être intéressé, disons avec une certaine probabilité. Ou bien, on pourrait renoncer à cette hypothèse un peu naïve que chaque candidat a une valeur intrinsèque et qu’il s’agit de recruter « le meilleur » ; dans ce cas, on peut supposer que l’ensemble des candidats est ce qu’on appelle un ensemble « partiellement ordonné », c’est-à-dire que parfois on se refuse à comparer deux candidats. Le problème est alors de recruter un candidat « maximal », c’est-à-dire qui n’est jugé inférieur à aucun autre, même s’il n’est pas comparable à d’autres. Ou bien, ou bien etc. Une multitude de problèmes de ce genre se présentent. Le propre des mathématiques est précisément de développer des méthodes qui peuvent être utilisées dans un grand nombre de cas. C’est ce qui se passe ici : il y a toute une théorie structurée qui se cache derrière tous ces problèmes. Les mots clés sont « temps d’arrêt », « martingale », « fonction harmonique » etc. Une fois les hypothèses bien formulées (et souvent elles ne sont pas aussi naïves que dans les exemples que nous venons de voir) la plupart des problèmes de ce genre sont résolus. Une théorie complètement mûre qui à son tour engendre des problèmes (et de solutions !) qui ont des retombées dans d’autres parties des mathématiques. Dans chaque cas, il faut se poser deux sortes de questions. Quelle est la nature de l’information partielle dont je dispose aux moments où je suis amené à me décider ; est-elle qualitative (comme des comparaisons) ou bien quantitative ? Mais aussi, il faut se demander quel est le but recherché, quelle est la quantité aléatoire qu’on cherche à optimiser. Ces deux questions sont bien sûr le plus souvent du ressort du modélisateur.

Des méthodes utiles en pratique ? Oui et non. Non, car il ne faudrait pas croire qu’on peut ramener tous les processus de décisions humains à de froids calculs de cette sorte. Oui, car au moins elles peuvent donner des idées générales, des indications sur les erreurs à ne pas commettre, comme celle qui consisterait à prendre des décisions trop rapides par exemple... Mais aussi, on peut imaginer un grand nombre de situations concrètes où on aimerait bien qu’une machine prenne des décisions. Par exemple une machine peut mesurer un signal aléatoire qui suit une loi de probabilité connue, qui peut être un paramètre biologique d’un malade, un cours de la bourse, ou encore des vibrations sismiques. A un certain moment, le régime peut changer pour une autre loi de probabilité, peut-être très légèrement différente. Comment enseigner à une machine que quelque chose a changé, comment lui enseigner à « tirer la sonnette d’alarme » au bon moment, si possible sans se tromper ? Utile pour détecter une attaque, une crise boursière ou un tremblement de Terre. Dans ce genre de situations, une stratégie précise, bien établie mathématiquement, est une nécessité.

Des preuves ?

$ $
Ce paragraphe est beaucoup plus difficile à lire que les autres mais on peut heureusement s’en passer ! N’hésitez pas à le sauter.... Ce serait dommage cependant car les maths n’existeraient pas sans les preuves. Nous allons nous contenter ici d’expliquer une seule preuve — celle de la meilleure stratégie pour le problème des secrétaires — et nous devrons nous contenter de donner des références pour les autres problèmes que nous avons cités. Essayons-donc d’expliquer le mystérieux 37 %.

Supposons donc que $n$ candidats se présentent et que nous cherchions la meilleure stratégie pour trouver le meilleur. Avant de déterminer la meilleure stratégie, commençons par en décrire quelques unes, peut-être pas les meilleures... Fixons un entier $i$ qui est compris entre 1 et $n$ et définissons une stratégie qui dépend de cet entier $i$ et que nous noterons $Strat_{i,n}$. C’est simple : il s’agit d’observer les $i$ premiers candidats sans rien décider puis de choisir le premier qui se présente et qui est meilleur que tous ceux qui le précèdent. Par exemple, la stratégie pour $i=n$ n’est pas très intéressante : elle consiste à ne rien faire et à prendre finalement le dernier candidat ! On comprend qu’avec cette « stratégie » $Strat_{n,n}$, on trouvera le meilleur uniquement s’il se présente en dernier : il y a une chance sur $n$ que cela arrive.

Dans un premier temps, nous allons fixer $n$ et $i$ et nous allons calculer la probabilité de trouver le meilleur candidat avec la stratégie $Strat_{i,n}$. A priori, on ne sait pas bien sûr quand se présentera ce meilleur candidat. Cela peut être le premier, le second, ..., jusqu’au $n$-ème. Appelons $k$ la position (inconnue) du meilleur. Il y a une chance sur $n$ que $k$ prenne chacune des valeurs possibles $1,2, ..., n$.

Maintenant, si on applique la stratégie $Strat_{i,n}$, on va trouver le meilleur si (et seulement si) deux conditions sont satisfaites :

• d’une part le meilleur, que nous avons noté $k$, est situé après $i$ (car sinon on aurait « laissé passer » le meilleur dans la période d’observation des $i$ premiers pendant laquelle on ne prenait aucune décision) et,

• d’autre part le meilleur dans la liste $1,2, ..., k-1$ est situé avant $i$ (car sinon celui-ci qui passerait devant la directrice pendant la période de décision, et il serait recruté « par erreur » à la place du meilleur de tous, en l’occurence $k$). Cette deuxième condition est réalisée avec une probabilité $i/(k-1)$ (nous supposons ici que $i$ et $k$ sont fixés).

En résumé, $i$ étant toujours fixé, et si $k$ prend successivement les valeurs $1, 2, ..., i$ la probabilité de trouver le meilleur est 0 ; et ensuite lorsque $k$ prend les valeurs suivantes $i+1, i+2, ..., n$, elle est $i/(k-1)$. Puisque $k$ prend chaque valeur avec la même probabilité $1/n$, la probabilité $P_{i,n}$ de trouver le meilleur avec la stratégie $Strat_{i,n}$ est :

\[ P_{i,n}= \frac{1}{n}. 0 + ... + \frac{1}{n}. 0 + \frac{1}{n}.\frac{i}{i}+\frac{1}{n}. \frac{i}{i+1} + \frac{1}{n}.\frac{i}{i+2} + ... + \frac{1}{n}.\frac{i}{n-1} = \frac{i}{n} ( \frac{1}{i}+ \frac{1}{i+1} + \frac{1}{i+2} + ... + \frac{1}{n-1} ). \]

Ainsi, pour chaque $n$, on peut calculer successivement les nombres $P_{i,n}$ pour $i=1, ..., n$ et chercher le plus grand : celui qui donnera la meilleure stratégie parmi les $Strat_{i,n}$ avec un nombre de candidats $n$ fixé. On peut faire cela avec une calculette pour les petites valeurs de $n$. Par exemple, pour $n=10$, le meilleur $i$ est $i=4$. Mais cela est peu pratique : ce n’est faisable que si $n$ n’est pas trop grand. Pour des valeurs de $n$ plus grandes, on peut utiliser quelques approximations. Si vous connaissez quelques rudiments de calcul intégral, on peut voir dans la somme $ \frac{1}{i}+ \frac{1}{i+1} + \frac{1}{i+2} + ... + \frac{1}{n-1} $ une approximation de l’intégrale $\int_i^n \frac{dx}{x}$ qui est donnée par un logarithme $\ln (n/i)$. Ainsi la quantité $P_{i,n}$ dont il s’agit de trouver le maximum pour une valeur de $n$ donnée est proche de $x \ln(1/x)$ avec $x=i/n$ et nous sommes donc amenés à résoudre un problème classique : trouver le maximum de $x \ln(1/x)$ pour $x$ dans l’ntervalle $[0,1]$. Facile ! il suffit de chercher où la dérivée s’annule. On trouve donc $\ln(1/x) - 1= 0$ si bien que finalement $x= 1/e$ où $e=2,71828...$ est la base des logarithmes népériens. On a donc $i/n \simeq 1/2,71828 \simeq 0,37...$ et voilà, nous avons notre 37 %.

Reste à se convaincre qu’il n’est pas utile de chercher d’autres stratégies que les $Strat_{i,n}$ : les autres seront moins bonnes. Il faut d’abord bien comprendre un mot que nous avons déjà employé souvent : stratégie.
Considérons la situation après la $l$-ème audition. Quel est l’état de la connaissance de la directrice ? Elle a vu passer $l$ candidats : baptisons-les $C_1,C_2,C_3, ..., C_l$ et elle les a classés. La seule information dont elle dispose est ce classement (n’oubliez pas que cette hypothèse est critiquable, que dans la « vraie vie », elle dispose d’informations d’autres natures, mais c’est quand même l’hypothèse que nous faisons !). Par exemple, pour $l=2$ ; deux situations peuvent se produire, qu’on notera bien sûr $C_2\lt C_1$ et $C_1\lt C_2$ suivant que c’est le premier ou le second des deux qui est le meilleur des deux. Pour $l=3$, on a six possibilités qui sont :

\[C_1\lt C_2\lt C_3 \quad C_2\lt C_1\lt C_3 \quad C_1\lt C_3\lt C_2 \quad C_3\lt C_1\lt C_2 \quad C_2\lt C_3\lt C_1 \quad C_3\lt C_2\lt C_1. \]

Comme on le voit, il y aura en général $l ! = l(l-1)(l-2) ... 3.2.1$ possibilités d’ordres entre les $l$ premiers candidats qui se présentent. Lorsque le candidat $C_{l+1}$ se présente, la directrice peut le placer par rapport aux précédents qu’elle a déjà ordonnés ; elle peut le faire de $l+1$ façons bien sûr. Une stratégie est alors une façon de choisir a priori, avant de voir défiler les candidats, une décision (j’embauche ou je continue les auditions ?) pour chaque $l$ et pour chacun de ces
$l !$ ordres entre $C_1, ..., C_l$. Lorsqu’on a choisi une stratégie et qu’on tire au hasard un ordre de passage des $n$ candidats, on voit passer d’abord 1, puis 2, ..., puis $l$ candidats, jusqu’au $n$-ème et dernier. A chaque passage, notre stratégie nous dit s’il faut voir le suivant ou s’il faut embaucher (et alors on ne voit pas les suivants en fait). Pour chaque stratégie, il y a une certaine probabilité qu’elle mène au recrutement du meilleur de tous les candidats. Et il s’agit de trouver une stratégie qui rend cette probabilité aussi grande que possible.

Une chose est claire : si le dernier candidat examiné $C_l$ n’est pas le meilleur de ceux que nous avons vus auparavant, il est inutile de le choisir puisque nous savons qu’il n’est pas le meilleur ! Les seuls cas où nous pourrions décider de prendre la décision d’embauche est celui où $C_l$ est meilleur que $C_1, C_2, ..., C_{l-1}$. Disons pour simplifier qu’un candidat est un bon candidat s’il est meilleur que tous ses prédécesseurs. Notre problème est donc le suivant :
Supposons que $C_l$ soit un bon candidat : faut-il l’embaucher ?
A priori, la réponse peut dépendre des autres informations dont la directrice dispose, c’est-à-dire la manière dont les $l-1$ qui le précèdent sont ordonnés. Mais en fait, en quoi ces informations pourraient nous dire quelque chose sur ce que nous cherchons : le meilleur parmi tous ? La meilleure stratégie ne devrait pas tenir compte de cela.
Voici comment on peut s’en convaincre. Partons d’une stratégie et observons la situation quand $l=3$. Ici $C_3$ peut être un bon candidat de deux manières possibles
$C_1\lt C_2\lt C_3$ et $C_2\lt C_1\lt C_3$. Ces deux situations se produisent avec la même probabilité ($1/6$ chacune). Par la suite, lorsque $C_4,C_5, ..., C_n$ se présentent, on comprend qu’il se passe la même chose dans les deux cas, à ceci près que $C_1$ et $C_2$ sont inversés. Si on sait que le meilleur n’est ni $C_1$ ni $C_2$, le fait de les intervertir ne changera rien à la position du meilleur. Si on considère donc les deux stratégies qui suivent $C_1\lt C_2\lt C_3$ et $C_2\lt C_1\lt C_3$, on peut tout simplement supprimer celle des deux qui est la moins bonne, qui donne la plus petite probabilité de trouver le meilleur, et la remplacer par l’autre, la meilleure des deux, bien sûr après avoir permuté $C_1$ et $C_2$. En clair, après cette manipulation, on aura une nouvelle stratégie globale, meilleure que la première, et qui prend la même décision après les deux situations $C_1\lt C_2\lt C_3$ et $C_2\lt C_1\lt C_3$. Ce même argument fonctionne pour toutes les valeurs de $l$. Une meilleure stratégie doit donc avoir la propriété suivante : elle doit décider de la même manière (j’embauche ou je continue les auditions ?) pour deux bons candidats $C_l$, indépendamment donc de l’ordre des précédents. Pour décrire une stratégie optimale, il nous faut donc décider d’un certain nombre de valeurs $l$ dites « d’observation » pour lesquelles on continue les entretiens après le $l$-ème, même si le $l$-ème était un bon candidat. Maintenant un instant de réflexion (ou peut-être deux !) montre que ces valeurs « d’observation » doivent être consécutives et former un ensemble de la forme $1, 2, 3, ..., i$ pour un certain entier $i$. Voilà, nous avons démontré que notre stratégie optimale est nécessairement de la forme $Strat_{i,n}$. CQFD.

Une remarque de bon sens pour conclure

Il y a quelques années, alors que j’expliquais le « théorème des secrétaires » à des non mathématiciens, et que j’expliquais aussi cette interprétation ridicule que certains en donnent en termes de choix d’une épouse, on m’a fait une remarque intéressante : « Votre démonstration mathématique n’a oublié qu’une seule chose : le coup de foudre ! » Certes !

Des références bibliographiques

$ $
Thomas Ferguson est l’un des spécialistes du sujet. Sur son site, on trouvera une sélection d’articles (en anglais) qu’on peut télécharger. Même s’il est un peu ancien, son article
« Who solved the secretary problem ? Statistical science, volume 4, pp.282-296. 1989 » est passionnant.