Vous êtes face à un immeuble de 100 étages avec 2 noix de coco identiques dans la main.
Vous pouvez jeter chaque noix de coco de n’importe quel étage, tant qu’elle ne casse pas vous pouvez la réutiliser.
Le but est de trouver l’étage le plus bas pour lequel la noix de coco se casse.
Il faut trouver une méthode qui minimise le nombre de lancers pour trouver cet étage (dans le pire des cas)
Exemple (idiot): je lance la première noix de coco du 50e étage.
- si elle casse je lance la deuxième noix de coco du 1er, puis du 2e, ainsi de suite jusqu’à qu’elle casse → au pire 1+49=50
- si elle ne casse pas, je continue 51e, 52e… jusqu’à 99 → 50 coups
Je trouverai l’étage à coup sûr, en 50 coups maximum.
Ben j’applique une force mesurée d’impact sur la noix de coco n°1 à l’aide d’un marteau pour voir la limite. Je tape donc de plus en plus fort jusqu’à ce que ça casse.
Ensuite, avec un peu de physique, je calcule la hauteur de chute nécessaire pour obtenir cette force. J’en déduis l’étage.
Total : 0 lancés.
Keiyan, peut pas faire moins.
Salut !
Je dirai bêtement 33 lancés (en supposant qu’elles cassent au moins lancées du 100 éme étage). Et j’espère qu’il y a un ascenseur… 
Fred
Je lance des étages suivants (tant que la première ne se casse pas):
14
27
39
50
60
69
77
84
90
95
99
Dès que la première se casse, je teste tous les étages entre les deux derniers lancers. 14 lancers dans le pire des cas.
Enorme Genji !
Et si jamais on a autant de noix de cocos qu’on veut ?
titoufred dit:Enorme Genji !
Et si jamais on a autant de noix de cocos qu'on veut ?
Je dirais une simple recherche dichotomique, donc on doit être à 9 lancers dans le pire des cas.
Oui, c’est sûr !
je lance sur l’herbe, la noix de coco dans un sac rempli d’eau, même du 100ème elle devrais pas cassé ( sauf si un badaud est en dessous 
)
genji dit:la solution
Salut !
Super !
Mais par quel truchement en arrive-t-on à ce résultat ou quoi ? Fred
- Tu lances à 14, elle casse.
- Tu lances à 7, elle casse.
Tu sais pas si elle arrête de casser à 1, 2, 3, 4, 5, ou 6…
Triz dit:- Tu lances à 14, elle casse.
- Tu lances à 7, elle casse.
Tu sais pas si elle arrête de casser à 1, 2, 3, 4, 5, ou 6...
Alors non, c'est pas ça, c'est ça :
- Lancée au 14ème étage, la 1ère casse
- on lance la 2nde du 1er étage
- si elle n'a pas cassée, du 2ème
- si elle n'a pas cassée, du 3ème
- etc...
Fred
Flash Solaar dit:
Super !
Généralement, quand il faut minimiser une quantité dans le pire des cas, tu cherches à ce que tous les cas soient sensiblement identiques.
Tu sais que, une fois que la première noix de coco sera cassée, il faudra tester tous les étages un par un entre le plus haut étage où elle a résisté et celui où elle a cassé.
Pour que la somme des lancers de la première noix de coco (qui te sert à trouver l'intervalle en question) et de ceux de la deuxième (pour parcourir l'intervalle) soit constante, il faut que la taille de l'intervalle à tester décroisse quand le nombre de lancers pour trouver cet intervalle augmente.
Il ne reste plus qu'à trouver le bon écart initial pour arriver au moins jusqu'à 100 et c'est fini.
Merci pour cette réponse.
Encore une question : alors du coup pour trouver le bon écart initial, c’est fait de manière empirique ? Style genre, on essaie avec 12, c’est trop petit, alors on essaye avec 20, ça marche mais on essaye plus petit (genre avec 16), etc… ou quoi ? 
Fred
Flash Solaar dit:Merci pour cette réponse.
Encore une question : alors du coup pour trouver le bon écart initial, c'est fait de manière empirique ? Style genre, on essaie avec 12, c'est trop petit, alors on essaye avec 20, ça marche mais on essaye plus petit (genre avec 16), etc... ou quoi ?
Fred
Si on commence à k, le deuxième intervalle fera k-1, le troisième k-2 et ainsi de suite. On pourra ainsi monter jusqu'à:
k + (k-1) + (k-2) + ... + 2 + 1 = k*(k+1)/2
Il faut donc trouver le plus petit k tel que k*(k+1)/2 soit supérieur à 100, ce qui nous donne k = 14.
Quelle pourrait être la stratégie si l’on possède 3 noix de coco ?
titoufred dit:Quelle pourrait être la stratégie si l'on possède 3 noix de coco ?
On fait une récursion. Avec une noix de coco, k lancers permet de couvrir un intervalle de taille k. Avec deux noix de coco, k lancers permettent de couvrir un intervalle de taille k(k+1)/2 (cf mon raisonnement précédent).
La troisième noix va donc séparer [0, 100] en intervalles de taille k(k+1)/2 pour k décroissant de 1 à chaque fois.
Il faut donc, comme pour le problème initial, calculer
somme{k = 1 à n} k(k+1)/2 = n(n+1)(n+2)/6
On cherche donc le plus petit entier n tel que n(n+1)(n+2)/6 > 100 et on trouve n = 8. La première noix de coco doit donc être lancée aux étages:
- 36 (8*9/2)
- 54 (36 + 7*8/2)
- 75 (54 + 6*7/2)
- 90
- 100
Puis, selon l'intervalle choisi, on utilise la stratégie à deux noix de coco avec le bon k (k = 8 pour le premier intervalle, 7 pour le deuxième, ...). Le nombre total de lancers est donc 9. En effet, je me suis débrouillé pour que le nombre de lancers soit le même quel que soit l'étage où casse la première noix de coco lancée. Il suffit donc de regarder si elle se casse dès le début:
- 1 lancer pour la première noix de coco
- 8 lancers au total pour les suivantes puisque l'intervalle est plus petit que 8*9/2.
Notes:
- l'intervalle doit en fait faire k(k+1)/2 + 1 mais ça rendait le raisonnement moins clair, à mon sens
- on doit arriver à encore moins de lancers avec 4 noix de coco, ce qui contredit ma réponse sur la recherche dichotomique. Je vais y réfléchir.
En fait, pour la dichotomie (cas des noix de coco à volonté), c’est seulement 7 lancers : 2,4,8,16,32,64,128.
titoufred dit:En fait, pour la dichotomie (cas des noix de coco à volonté), c'est seulement 7 lancers : 2,4,8,16,32,64,128.
Je sais, mais j'avais l'impression qu'on arrivait à moins que ça avec 4 noix de coco. Je vérifierai...
Si l’on note f(n,k) le nombre d’étages couverts par n noix de cocos en k lancers, alors on peut trouver la relation de récurrence :
f(n,k) = Somme{pour i=1 à k-1, f(n-1,i)} + 2 (pour n>0 et k>0).
De proche en proche, il vient :
f(0,k)=1
f(1,k)=k+1
f(2,k)=k(k+1)/2 + 1
f(3,k)=k(k^2+5)/6 + 1
f(4,k)=k(k-1)(k(k-1)+10)/24 + k+1
A vérifier, mais je pense que c’est bon car f(k,k)=2^k
f(3,8 )=93 et f(3,9)=129 donc 9 lancers pour 3 noix.
f(4,7)=99 et f(4,8 )=163 donc 8 lancers pour 4 noix.
Super genji j’ai rien besoin de rajouter, c’est parfait 