|
#1 - 09-10-2009 23:28:51
- VanSS
- Habitué de Prise2Tete
- Enigmes résolues : 47
- Messages : 31
Boulse de cristal
Un petit problème posé au concours d'admission de X polytechnique, enfin il parait, je n'y étais pas
On veut determiner avec précision à partir de quelle hauteur des boules de cristal se cassent. Pour cela on peut les lancer à differents étages d'un immeuble de 120 étages et on veut trouver l'étage limite, c'est à dire, à partir de cet étage et aux étages supérieurs elles cassent par en contre aux étages inférieurs elles ne cassent pas.
Quel est le nombre de lancer minimum et la stratégie à utiliser pour etre sur de trouver l'étage limite avec seulement 2 boules de cristal?
#2 - 09-10-2009 23:34:55
- papiauche
- Sa Sainteté
- Enigmes résolues : 49
- Messages : 2131
boules de crostal
Je dirais quinze lancers aux maximum.
1. 15 2. 29 =15 +14 3. 42 = 29+ 13 ... 13. 117 = 114+3 14. 119 = 117 +2 15. 120= 119+1
Je commence à 15.
Si la première boule se casse, je repars du 1er et j'ai 14 essais au maximum pour que la deuxième se casse --> 15 au plus.
Si elle ne casse pas, je passe au 29 (si elle se casse, je repars du 16 et j'ai 13 essais maximum pour que la deuxième se casse ---> 15 au plus)
Sinon je passe au 42. (si elle se casse, je repars du 30 +12 essais maximum --->15 au plus) etc...
Si elle doit se casser au 120ème étage, j'en serai à 15 lancers avec cette méthode. Et une chance sur quinze que la deuxième reste intacte.
"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde
#3 - 09-10-2009 23:48:08
- scrablor
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 965
bouled de cristal
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.
Celui qui fuit les casse-tête ne vaut pas un clou.
#4 - 10-10-2009 00:39:07
- gabrielduflot
- Expert de Prise2Tete
- Enigmes résolues : 34
- Messages : 609
Boules de cirstal
7 lancers. on commence au 60 eme et on fait comme on dit en maths par dichotomie Si ca se casse tu vas au 30eme sinon tu vas au 90eme
#5 - 10-10-2009 03:58:50
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Boules e cristal
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.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#6 - 10-10-2009 15:36:19
oules de cristal
J'ai trouvé 15. Le tout est de penser en dégressif.
#7 - 10-10-2009 15:48:48
- moicestmoi
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1617
- Lieu: Avec vous :-)
boules de cristam
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.
L'angle droit bout à 90 degrés.
#8 - 10-10-2009 23:43:52
- Damnation
- Professionnel de Prise2Tete
- Enigmes résolues : 24
- Messages : 208
boules de cristzl
Sachant qu'elle est en cristal, elle se casse dès le premier etage Ok C'est bon je suis deja dehors ----> [ -]
#9 - 11-10-2009 03:09:38
- kosmogol
- Banni
- Enigmes résolues : 49
- Messages : 11,928E+3
Bouels de cristal
h/2 +1
-- Les messages doivent avoir une contenance minimum de 15 caractères.
http://enigmusique.blogspot.com/
#10 - 12-10-2009 11:13:10
- Enelya!
- Professionnel de Prise2Tete
- Enigmes résolues : 13
- Messages : 117
bpules de cristal
Je dirais 2 lancés minimum, ça dépend de la hauteur... La technique serrait de monté les étages 4 par 4 jusqu'à ce que la boulet casse. Dans ce cas là on descend de 2 étages on l'a lance... Si elle casse, c'est en dessous, si elle ne casse pas, on lance au dessus, si elle casse, c'est que c'est là, sinon, c'est au dessus.
Explication : avec un lancer on peut tester de boules, donc avec 2 boules, on peut testé 2*2 étages. Si nous avions eu 3 boules, nous aurions pu faire les étages deux par deux.
#11 - 12-10-2009 13:41:50
- dylasse
- Professionnel de Prise2Tete
- Enigmes résolues : 21
- Messages : 378
bouleq de cristal
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é.
#12 - 12-10-2009 17:29:34
- Bamby2
- Professionnel de Prise2Tete
- Enigmes résolues : 0
- Messages : 152
boulrs de cristal
je dirais qu'il faut en lâcher une tous les 2 étages, puis redescendre si ça casse, voire a quelle étage exactement. en tout ((n+1)modulo 2) +1).
#13 - 12-10-2009 18:33:19
- Flying_pyros
- Sage de Prise2Tete
- Enigmes résolues : 48
- Messages : 3418
- Lieu: Près de la mer
biules de cristal
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+
#14 - 12-10-2009 21:15:31
- djeuns
- Habitué de Prise2Tete
- Enigmes résolues : 24
- Messages : 30
boyles de cristal
on commence avec 1 boule du RDC puis on monte au fur et a mesure des qu elle casse on redescend d un etage et on reessaye avec la 2eme boule si elle ne casse pas on a trouver l etage limte : au dessus ca casse
#15 - 12-10-2009 23:42:14
- kosmogol
- Banni
- Enigmes résolues : 49
- Messages : 11,928E+3
boukes de cristal
Je me suis fait avoir dans cette histoire, bravo !
http://enigmusique.blogspot.com/
#16 - 12-10-2009 23:52:29
- papiauche
- Sa Sainteté
- Enigmes résolues : 49
- Messages : 2131
boules de cristak
"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde
#17 - 13-10-2009 09:18:52
- Enelya!
- Professionnel de Prise2Tete
- Enigmes résolues : 13
- Messages : 117
#18 - 13-10-2009 10:16:20
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
bouled de cristal
En effet, superbe... Et appliquable à tous les nombres, suffit de trouver le plus petit [latex]n[/latex] tel que le nombre d'étages du building est inférieur ou égal à [latex]\frac{n(n+1)}{2}[/latex], et pis vendu.
Très joli coup. Du haut de tes 91 ans, t'es admissible aux X ("et quoi de mieux qu'une carrière X à cet âge canonique ?" dirait ash à ma place)
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#19 - 13-10-2009 15:27:15
- VanSS
- Habitué de Prise2Tete
- Enigmes résolues : 47
- Messages : 31
boules se cristal
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
#20 - 13-10-2009 15:36:34
- kosmogol
- Banni
- Enigmes résolues : 49
- Messages : 11,928E+3
boules de crustal
http://enigmusique.blogspot.com/
#21 - 13-10-2009 16:45:50
- Bamby2
- Professionnel de Prise2Tete
- Enigmes résolues : 0
- Messages : 152
bouled de cristal
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.
#22 - 05-11-2010 21:36:37
Boules de crista
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.
papiauche a écrit:Je dirais quinze lancers aux maximum. 1. 15 2. 29 =15 +14 3. 42 = 29+ 13 ... 13. 117 = 114+3 14. 119 = 117 +2 15. 120= 119+1
Je commence à 15.
Si la première boule se casse, je repars du 1er et j'ai 14 essais au maximum pour que la deuxième se casse --> 15 au plus.
Si elle ne casse pas, je passe au 29 (si elle se casse, je repars du 16 et j'ai 13 essais maximum pour que la deuxième se casse ---> 15 au plus)
Sinon je passe au 42. (si elle se casse, je repars du 30 +12 essais maximum --->15 au plus) etc...
Si elle doit se casser au 120ème étage, j'en serai à 15 lancers avec cette méthode. Et une chance sur quinze que la deuxième reste intacte.
#23 - 15-11-2010 21:30:21
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Boules de crsital
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 :-)
#24 - 15-11-2010 22:38:01
- engine
- Professionnel de Prise2Tete
- Enigmes résolues : 37
- Messages : 351
bpules de cristal
J'ai pas trouvé, j'ai les boules...
plouf
#25 - 16-11-2010 14:46:29
- Nicouj
- Professionnel de Prise2Tete
- Enigmes résolues : 27
- Messages : 330
boules de criqtal
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.
Mots clés des moteurs de recherche
|
|