Enigme
John adore les fleurs. Il possède des pots de fleurs identiques. Il aimerait tester leur résistance et savoir à partir de quelle hauteur ils se cassent. Il dispose de 2 pots qu’il peut casser en les lançant à partir des balcons d’un immeuble de 105 étages.
Il voudrait trouver, s’il existe, l’étage limite : celui en dessous duquel ses pots ne cassent pas, mais à partir duquel les pots cassent (ainsi qu’aux étages supérieurs).
John le fainéant recherche une stratégie qui lui assure le moins de lancers possibles dans le pire des cas avec la certitude de trouver l’étage limite (avec seulement 2 pots).
Quel est le nombre minimum de lancers et quelle stratégie John doit-il utiliser ?
Solution proposée par Nicolas, gagnant du casse-tête Eté 2015
1/ Si l’on veut trouver l’étage exact, la stratégie pour le pot n°2 sera forcément de tester étage par étage, à partir du dernier étage ou le pot n°1 n’a pas cassé.
2/ Si l’on veut optimiser uniquement le pire cas, celui-ci se produit lorsque l’étage où les pots cassent est celui où le pot n°1 a cassé (ou celui juste en dessous). Donc si l’on veut optimiser le nombre de lancers total, il faut réduire de 1 le nombre d’étages d’écart à chaque lancer du pot n°1.
3/ Reste donc à trouver l’étage du premier lancer pour le pot n°1, c’est à dire le plus petit nombre suffisamment grand pour que la somme en diminuant de 1 à chaque fois permette d’atteindre l’étage 105, et la réponse est 14 !
La stratégie est donc de lancer le premier pot aux étages suivants :
14
27 (14 + 13)
39 (27 + 12)
50 (39 + 11)
60 (50 + 10)
69 (60 + 9)
77 (69 + 8)
84 (77 + 7)
90 (84 + 6)
95 etc …
99
102
104
105
Le pire cas sera toujours de 14 lancers. En effet, à chaque nouveau lancer du pot n°1, on aura 1 lancer de moins à faire avec le pot n°2 si le pot n°1 casse.