Il faut d'abord admettre - et j'ai un peu de mal - qu'une boule qui a résisté à une chute n'a pas perdu un peu de sa résistance. J'admets aussi qu'elle ne casse pas si on la lâche au rez-de-chaussée...

Je lance la première boule des étages 3, puis 6, puis 9... jusqu'à ce qu'elle casse.
Elle casse donc à l'étage 3n.
Je lance l'autre à l'étage 3n-2 puis, si possible, 3n-1.

Si x désigne le premier étage fatal pour la boule, j'ai dû faire un nombre d'essais égal à :
E((x+1)/3) + 2 - où E est la fonction "partie entière" - avec 1 chance sur 3 de garder une boule intacte.

AU hasard, je dirais que
1) soit on considere que cet etage peut etre n'importe quel etage y compris le dernier.
On prend la racine carrée de 120, soit 11 approximativement.
on lance la premiere boule tous les 11 etages, donc aux étages:
11, 22, 33, 44, 55, 66, 77, 88, 99 et 110
et quand elle se casse, on prend le dernier etage ou elle ne s'est pas cassée, et avec l'autre boule on essaye tous les etages.
Par exemple, si la premiere boule s'est cassée au 66eme,
avec la 2eme, on essay les 56, 57, 58, 59, 60, 61, 62, 63, 64 et 65, jusqu'a ce qu'elle se casse.
Au maximum on aura 20 essais.
On peut aussi:
2) estimer que la boule se cassera probablement par exemple entre le 10eme et le 60eme etage, basé sur des calculs incluant la resistance des materiaux... etc
et faire un test reduit tous les 7 etages pour la remiere boule, et tous les etages pour la 2eme, avec un maximum de tests de 15.

Ah bon, on peut ouvrir des fenêtres dans des immeubles aussi hauts ?
Sauf peut-être aux tout derniers étages pour accéder aux toits...
En tout cas, ça pourrait répondre à ta question.

h/2 +1

--
Les messages doivent avoir une contenance minimum de 15 caractères.

Problème général :

Si on prend l'énoncé à la lettre, à chaque lacher de boule à une hauteur h, on reçoit l'information binaire : "casse" ou "ne casse pas", et on sait que si ça casse pour la hauteur h, ça casse pour la hauteur supérieures et que si ça ne casse pas pour la hauteur j, ça ne casse pas pour toutes les hauteurs inférieures.

L'optimisation du nombre d'essai d'un tel problème se fait par dychotomie (=coupage en deux).

On essaie à 60, puis 30 ou 90 suivant le résultat, etc...

On s'arrête quand on a l'info : à h ça ne casse pas et à h+1 ça casse.
Donc il faut réduire à 1 la longueur de notre intervalle final*.

comme 2 puis 6 < 120 < 2 puis 7, il faut 7 essais pour être sur de trouver le bon étage.

Problème particulier :

L'énoncé semble dire que 2 boules sont suffisantes, celà signifie que les 2 lachers se font à la hauteur cherchée h et à la hauteur h-1.

Je rajoute à l'énoncé que si ça casse pour h=1, alors la réponse est h=1 et on le prouve avec un lancer à h=1 et si ça ne casse pas pour h=120 alors la réponse est h>120 et on le prouve avec un lancer à l'étage 120.

La stratégie consiste donc à avoir beaucoup de chance dans le choix de la première hauteur... et à maximiser cette chance.

Si on choisit entre 3 et 118 :

Nous avons 1/121 chance de tomber sur la hauteur cherchée h0 (et de tester ensuite à h0-1) et 1/121 chance de tomber sur h0-1 (et de tester ensuite à h0), donc dans ces 2 cas nous auront déterminé h0.

Nous avons dans ce cas 2 chances sur 121.

Si l'on commence avec la hauteur 2 ou 119, on a le même pourcentage de change d'avoir 2 résultats différents qui permettent d'encadrer h0.
Par contre, si on a choisi 2 et que ca casse dès 1, sans encadrer h0, on aura la réponse (de même si ça ne casse pas à 120).

Donc si on choisi la hauteur initiale 2 ou 119, on a 3 chances sur 121 de trouver la bonne hauteur.

Donc la stratégie consiste à choisr en hauteur initiale 2 ou 119, nous auront alors 3 chance sur 121 de prouver en 2 lancers seulement quelle est la hauteur de casse.

Et comme on parle de cristal, le risque étant important que ça casse à faible hauteur, je choisirais donc de commencer à h=2 (en plus c'est moins fatiguant et je limite les risques d'avoir des débris à ramasser puisque dans seulement 2 cas sur 121 ma première boule va casser et 1/2 pour la deuxieme si la premiere a cassé et 1/119 la deuxieme si la premiere n'a pas cassé...)

problème personnel (ajouté après lecture des autres réponses...) :
Avant de se lancer dans des démonstrations fumeuses, il faut comprendre l'énoncé : une petite confusion entre "lancer" et "boule" m'a fait écrire n'importe quoi. J'en suis désolé.

Hello,

Il faut voir la solution dans la boule de cristal !!!!
une fois l'étage vu dans la boule, on peut tester avec ses deux boules.

a+

Je me suis fait avoir dans cette histoire, bravo !

Bien vue papiauche !

En effet felicitations à papiauche et Zoslex qui ont trouvé la reponse optimale, vous avez presque tous pensé à utiliser la premiere boule pour trouver un palier mais toute l'astuce était de trouver que ces paliers ne devaient pas tous etre de la meme hauteur , vu que les derniers palieres ont nécessité plus de tests préalables.

Je ne réexplique pas en détail vu que papiauche l'a très bien fait. Effectivement Mths-MlndN cela revient à chercher un entier n tel que
n(n+1)/2 soit plus grand que le nombre d'etages. Pour ceux qui ne voient pas pourquoi, on remarque dans la solution que la hauteur du palier dimlinue de 1 à chaque fois jusqu'à obtenir en haut de l'immeuble un palier de 1 etage. Du coup cela revient à chercher n tel que la somme des nombres de 1 à n soit plus grande que la hauteur de l'immeuble. Cette somme vaut n(n-1)/2, c'est une formule bien connue. Pour la justifier je pourrais vous dire que je somme 1 avec n, 2 avec n-1, 3 avec n-2 et ainsi de suite de telle sorte que chaque somme partielle vaut n+1. Comme il se trouve que j'ai n/2 somme partielle de ce type, on a bien au final une somme globale de n(n+1)/2.

Voila, j'espere avoir été clair et que cet enigme vous a plu

han, j'avais raté le minimum, je trouvais le truc simple aussi
ça m'apprendra a faire les énigmes en 2 mins tiens, je suis passé a coté d'une plutôt sympa.

Merci Papiauche, j'avais déjà lu ta réponse, mais rien ne prouve son optimalité, surtout : comment trouve-t-on les étages-tests dans le cas général. ?

Enfin, depuis j'ai trouvé une preuve, assez facile d'ailleurs, mon seul regret est qu'elle utilise une dérivée dans une situation discrète et ça m'énerve :-)

Gasole a écrit:

Bonjour,

J'ai rencontré cette énigme cet après-midi, après avoir trouvé "la" solution, je me suis demandé comment prouver qu'elle est optimale... avez-vous une idée ?

Cordialement,

Olivier.

En fait on devrait montrer ça un peu de la même manière que l'on démontre que la complexité du tri de n éléments est n*log_2(n)

Voilà une idée informelle d'une preuve.

Quelque soit sa stratégie, on peut la représenter par un arbre, où les nœuds sont les étages où on fait un essai et ou les fils gauche représentent les essais suivants si la boule s'est cassée et les fils droit représentent les essais si la boule ne s'est pas cassée.
La stratégie optimale est donc celle qui minimise la hauteur de l'arbre qui la représente.
L'arbre représentant la solution à la forme

A
| A
|| A
||| A
|||| A
etc

Tous les sous arbres sont de même longueurs, on ne peut donc pas trouver d'arbre plus court. C'est donc bien une stratégie optimale.