Forum de mathématiques - Bibm@th.net

À Ernst,
merci beaucoup pour tes réponses détaillées même si elles me déçoivent en un sens. J'espérais un raisonnement que je n'aurais pas vu.

Personnellement j'ai fait une feuille de calcul sur tableur avec une erreur dans la première version, dont j'ai mis du temps à me rendre compte.
Il m'a semblé évident depuis le début qu'un pas constant ne peut pas être optimal car les derniers étages demandent plus de lancers.
Il faut donc diminuer la taille des tranches quand on monte.

Hello verdurin,

Oui, c'est bien cela, exploration exhaustive.

En fait peu importe la stratégie imaginée, elle se réduit toujours à une liste d'étages où l'on teste la première boule (par exemple [14, 27, 39, ...]) puis à une recherche linéaire entre deux tests consécutifs quand la première boule casse. Donc l'ensemble des stratégies possibles est l'ensemble de toutes les sous-listes croissantes d'étages entre 1 et 100. C'est un espace fini, dénombrable, et le programme va le parcourir entièrement.

Il met en jeu la programmation dynamique. Concrètement, le programme calcule d'abord le meilleur coût pour atteindre chaque étage avec 1 seul test, puis avec 2 tests en essayant tous les étages intermédiaires possibles, puis avec 3 tests, et ainsi de suite en s'appuyant sur les résultats précédents. À chaque étape et pour chaque état (étage atteint, nombre de tests utilisés) il essaie tous les prédécesseurs possibles et en garde un record. Aucun étage intermédiaire n'est jamais écarté sans avoir été comparé aux autres.

Le programme fait deux calculs indépendants, un calcul théorique par récurrence (rapide, basé sur des formules) et une simulation, pour chaque seuil de 1 à 100 il applique la stratégie trouvée et les deux résultats doivent coïncider. Ce n'est pas une approximation, c'est bien équivalent à essayer toutes les combinaisons, mais considérablement plus vite grâce à la mémorisation des résultats intermédiaires. La séquence [13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97] avec une moyenne de 10,30 lancers est donc bien un minimum (il y en a d'autres, le programme ne conserve que les premiers records), et pas seulement un bon résultat.

Bon, il semble que ça ne marche pas mieux. Plus ça va et moins je crois au sérieux de la réponse "10".

Bonjour,
Avec  19, 36, 51, 64, 75, 84, 91, 96, 99 pour la première boule, on arrive à un tout petit peu moins de 10 essais en moyenne (9,99 pour être précis).
Exemple : en conditionnant par "le n° d'étage fatidique est >64 et <= 75", le nombre moyen d'essais pour trouver ce n° est 
$$ 5 + \frac 1{75-64}\times \frac{(75-64-1)(75-64)}2 =10\;.$$
P.S. Erreur dans mon calcul ! Je reprends après déjeuner, en essayant de poursuivre l'idée : conditionner par tranches pour la valeur de la variable aléatoire, en visant la moyenne 10 pour chaque tranche.

Bonjour,

L'énigme avait été soumise pat Fred et tirée d'un entretien d'embauche chez PetitMou alias MicroSoft.
Voici la méthode qui avait développée par notre prof d'éco, bon matheux, spécialiste des calculs de Probas
Elle vaut ce qu'elle vaut, je n'en ai pas d'autre...

@+

J'ai vraiment du mal avec ce problème.
Voilà où j'en suis.

On fait une liste de n valeurs  croissantes $(a_1,\dots a_k,\dots  a_n)$ avec $a_n=100-1$.
On lance une boule de l'étage $a_1$ puis, si elle n'a pas cassé, de l'étage $a_2$ etc jusqu’à ce qu'elle casse.
Si elle n'a pas cassé à l'étage 99 on sait qu'elle va casser à l'étage 100 d'après l'énoncé. On peut donc s’arrêter.

Pour simplifier on pose $a_0=0$ et, pour $k$ entre 1 et $n$, $d_k=a_k-a_{k-1}.$
Si la boule casse à l'étage $a_k$ on lance la seconde boule à partir de l'étage $a_{k-1}+1$ jusqu’à ce qu'elle casse.
Si elle ne casse pas à l'étage $a_k-1$ on sait que l'étage cherché est $a_k.$

En résumé si la boule casse à un étage $B$ tel que $a_{k-1}<B<a_k$ il faut $k+B-a_{k-1}$ lancers pour trouver l'étage.

En regroupant les valeurs de $B$ vérifiant $a_{k-1}<B\leqslant a_k$ on voit qu'il faut au total $(k+1)+\dots+(k+d_k)-1$ essais.
Ce qui fait $k\,d_k+\frac12 d_k(d_k+1)-1$.

Finalement l'espérance est un centième de $\sum_{k=1}^n kd_k+\frac12\sum_{k=1}^n d_k(d_k+1).$

RE,

J'ai, moi, d'une part le résultat sec donné par PetitMou sans explication et d'autre part de la démo d'un amateur comme nous, matheux et qui était prof... d’Économie à Lausanne...
Grâce à cela, je peux dire  (En latin, on dit "doctus cum libro". Ici, ça s'applique à mon cas) que non, ton nombre moyen d'essais n'est pas encore optimal.....
Bon, tu ne peux pas encore (plus) descendre de beaucoup, mais tu peux encore descendre...

A en perdre le sommeil...

Je ne sais pas combien j'ai perdu en Elo.
J'ai arrêté de jouer aux Echecs en Club je ne supportais plus la tabagie ambiante et ma femme, lorsque je rentrais du Club m'envoyait me changer !
15 ans plus tard, lorsque le Club avait enfin pris la décision d'interdire de fumer, j'étais passé à une autre activité : le Kendo .
Hélas, le club a dû fermer, faute de prêt d'un gymnase muni d'un plancher...
On aurait pu continuer sur un de ces sols en Terraform : 3 mm de revêtement plastifié sur une dalle en béton.
Notre prof a dit niet ! on arrête ! Je ne veux pas prendre la responsabilité de vous laisser vous démonter la colonne vertébrale  et les articulations allant du bassin aux pieds (en Kendo, on doit taper du pied sur le sol à chaque frappe !!). Quant à "jouer" sur un tatami, c'était techniquement incompatible avec cet art martial...
On perdait trop de choses impossibles à réaliser et qui constituaient les fondements de notre pratique.

Chaque jour, je m'astreins  encore à essayer de résoudre le problème publié ici : https://www.europe-echecs.com/

@+

Bpnsoir verdurin,

Joli résultat,, tu tombes vraiment pas loin... Je dirais même que tu es assez proche
Mais tu dois encore un peu optimiser ta stratégie : ton nombre moyen d'essais est encore légèrement au dessus du résultat sec attendu et publié tel quel, sans explication par la Sté (PetitMou) qui aurait donné  ça pendant un temps-paraît_il dans ses tests d'embauche. Je me demande encore ce que ce truc leur apprenait.
J'avais cru comprendre qu'il fallait avoir une approche probabiliste, c'est pourquoi, elle demandait  d'établir uns stratégie qui permette << en moyenne, le moins de lancers possibles >>
Moi par tâtonnements j'étais arrivé à 19 sans pouvoir faire mieux (je n'avais pas véritablement de stratégie, un comble pour un joueur d'échecs qui faisait de la compétition !)

@+