Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 05-06-2007 09:40:10

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Enigme - Embauche chez Microsoft

Bonjour,

  Voici une petite énigme que je soumets à la sagacité des lecteurs du forum.
On dispose de deux boules en verre parfaitement identiques. On peut les lancer
d'un gratte-ciel de 100 étages, et on souhaite savoir à partir de quel étage
les boules cassent lorsqu'elles tombent au sol.
  Quelle est la stratégie optimale pour effectuer, en moyenne, le moins de lancers
possibles (sachant bien sûr que l'on ne dispose que de deux boules et que si
l'une casse, il faut déterminer l'étage avec l'autre, sans jamais la casser
avant l'étage fatidique!)?

  Pourquoi ce titre? Car il s'agissait d'une question utilisée dans les tests d'embauche chez
Microsoft. Et, pour la petite histoire, la firme américaine ne proposait pas la solution
optimale!

Fred.

Hors ligne

#2 05-06-2007 15:30:00

P.MTZ
Invité

Re : Enigme - Embauche chez Microsoft

bonjour,
Une réponse sans trop de réflexion! Si à l'ordre n (nième étage!) les boules sont intactes, on passe à l'ordre n+2, si la première boule résiste, on passe à l'ordre n+4, autrement on teste la 2ème boule à l'ordre n+1. Si elle casse, c'est lui, si non, c'est n+2; et, bien entendu, le premier test se fait à partir de l'ordre 2. On peut construire ainsi une fonction  f de  {1;...;100} dans [N qui à n associe le nombre d'essais.
Je ne sais si cette réponse est valide, mais en quelques minutes, c'est tout ce que j'ai trouvé;
Je viens de découvrir ce site et je l'apprécie. Je reviendrai... Bonne journée.

#3 05-06-2007 15:49:29

JJ
Membre
Inscription : 04-06-2007
Messages : 109

Re : Enigme - Embauche chez Microsoft

Bonjour,

La réponse logique me semble simple. Mais je peux faire erreur...
Ne voulant pas la donner prématurément, ce qui enlèverait le charme de la recherche, voici un pincipe qui semble être une lapalissade :
Puisqu'on a deux boules, on peut se permettre d'en casser une dès le début et du premier coup. Mais, bien sûr, en choississant pertinemment son coup..., pour que la seconde boule puisse être employée de la façon la plus optimum, minimisant le nombre total d'essais (et qu'elle donne le résultat certain lorsqu'elle casse).
@+

Hors ligne

#4 05-06-2007 18:12:47

P.MTZ
Membre
Inscription : 05-06-2007
Messages : 5

Re : Enigme - Embauche chez Microsoft

Il est vrai que l'option de lancer la première boule du 50ème étage est tentant... ce qui raméne le problème à 1 boule sur un immeuble de 49 étages OU un immeuble de 50 étages. Je n'ai pas fait le calcul, et donc je garderai ma réserve.

Hors ligne

#5 06-06-2007 00:14:24

k-lys
Membre
Inscription : 21-02-2007
Messages : 15

Re : Enigme - Embauche chez Microsoft

Comme première intuition :
Lancer tous les 2 étages n'est pas bon : dans le pire des cas (étage 99) il faut 51 coups.
Lancer du 50 dès le départ n'est pas mieux : 51 coups également (étage 99).
Je pense que le mieux est de trouver une stratégie qui prends en compte le fait que plus ca casse haut, plus il faut de coups avec la première boule. Dans ce cas, on commencerait à l'étage 15, puis 29 (15+14), puis 43 (29+13), etc. il faut ensuite trouver l'étage de départ optimal.
J'aurais donc tendance à dire, à cette heure si tardive, que le mieux est de lancer la première boule depuis les étages 14,27,39,50,60,69,77,84,90,95,99,100. (puisque la somme des entiers de 1 à 14 est égale à 105)
Les cas où il faut le plus de lancers sont les étages 13,26,...,98, et il suffit de 14 coups pour résoudre le problème. On peut même prendre un immeuble de 105 étages et avoir toujours un cas maximal de 14 coups.

Il y a peut-être mieux, mais à cette heure-ci je vais pas chercher plus loin.

Dernière modification par k-lys (06-06-2007 00:14:46)

Hors ligne

#6 07-06-2007 07:43:06

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Hello tous & toutes,

Il me semble que k-lys fait fausse route en raisonnant "pire cas".
La question est :
Quelle est la stratégie optimale pour effectuer, EN MOYENNE, le moins de lancers
possibles ?

Il me semble aussi qu'une hypothèse d'équiprobabilité de rupture (en fonction de la hauteur de chute) serait utile... la stratégie optimale étant évidemment différente pour une autre loi de proba.

Il me semble enfin qu'on puisse appliquer (sauf bug de ma mémoire) le th. de Belmann qui permet d'affirmer que si une stratégie est optimale elle l'est à chaque pas et donc en particulier au premier.

Nantis de celâââ... vous allez aboutir à la même conclusion que moâââ (ce qui ne veut pas dire que ce soit la bonne réponse !). Des objections ?
Comme JJ, je vous laisse plancher encore un peu, c'est le but du jeu.
A+

Bug mémoire effectivement !
Je voulais citer le "Principe d'optimalité de Bellman" qui s'énonce un peu différemment mais l'idée est bonne.
A+

Dernière modification par john (07-06-2007 08:54:11)

Hors ligne

#7 11-06-2007 15:58:09

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Enigme - Embauche chez Microsoft

Bon, je crois qu'une semaine de réflexion, ce n'est pas si mal...
John et JJ peuvent donner leur solution!

Fred.

Hors ligne

#8 12-06-2007 06:12:23

P.MTZZ
Invité

Re : Enigme - Embauche chez Microsoft

Bonjour!
Dans ce qui suit, k désigne un diviseur propre de 100 sauf 1, p(k) est le nombre total d'essais pour résoudre k étages avec une boule sachant que le kième à fait un sort à une boule, si R est un entier naturel (100, par exemple!), P(R) est le nombre total d'essais pour résoudre les R étages avec deux boules.
On a P(100) =   1 + p(k) + 1 + P(100-k) et en itérant P(100) = 200/k + (100/k)p(k). Or p(k) =k(k+1)/2 - 1 donc P(100)/100= (k+1)/2 + 1/k. En étudiant  sur [R+* la fonction f définie par f(x)= (x+1)/2 + 1/x  est décroissante jusqu'à sqrt(2) et croissante après... k=2 semble donc  idéal, pour la stratégie.

Ce raisonnement me paraît trop simple, voire trop beau.... J'ai pensé à cela cette nuit et je le livre de suite; car étant plus d'une formation maths pures (Paris VI et VII du début des années 70), j'ai en fait peu de connaissances en proba.....
                                        Bonne journée, même si vous me donnez des insomnies... A mon âge!!!

#9 12-06-2007 07:28:10

P.MTZ
Membre
Inscription : 05-06-2007
Messages : 5

Re : Enigme - Embauche chez Microsoft

P.MTZZ c'est moi, P.MTZ. Mais, étant donné mon âge avancé, je n'avais pas ciblé l'"onglet" identification. Maintenant, je comprends mieux pourquoi on me surnomme Zeimmer, et, surtout,  que les intimes me surnomment Al.....
Bonne journée à tous. Merci de motiver des envies de trouver, même s'il y a beaucoup d'impasses. L'important, c'est de chercher et d'apprendre!
    "Si une question mathématique se pose à vous, votre devoir est d'y répondre." C. Ehresmann. Paris 1975.

Hors ligne

#10 12-06-2007 07:38:53

k-lys
Membre
Inscription : 21-02-2007
Messages : 15

Re : Enigme - Embauche chez Microsoft

Oui, oui, je n'avais pas vu le "en moyenne", désolé.
Cependant, la solution que j'ai proposée nécessite en moyenne environ 10 coups (je n'ai pas fait le calcul, mais c'est à peu près ça), et il me semble que ce soit mieux que le lancer tous les deux étages, ou même le premier lancer à l'étage 50, qui tournent autour des 25 coups en moyenne...

Sauf erreur de ma part bien entendu.

Dernière modification par k-lys (12-06-2007 07:39:22)

Hors ligne

#11 12-06-2007 22:37:04

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Bonsoir à tous,
j'avais peur d'avoir rompu le fil en sortant de grosses théories mais je constate qu'il n'en est rien et c'est tant mieux. Pour l'instant je n'ai pas exploité ces idées et j'espère que Fred patientera jusqu'à la fin de la semaine.
Avec une espérance de #10 et à la main, je crois bien que k-lys reste(ra ?) en tête, car il va me falloir un PC pour minimiser une expression qui a beaucoup trop de paramètres. 
A+

Hors ligne

#12 13-06-2007 13:06:19

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Hello,
Je viens de calculer l'espérance de k-lys (avec la suite de pas : 14, 13, 12... 5, 4) et, SAUF ERREUR c'est tout à fait remarquable pour une solution "à la main". Elle est de 7.15 alors que les 2 stratégies optimales à pas constant (soit pas de 9, soit pas de 11) ont une espérance de 9,9.
Intuitivement, une stratégie à pas proportionnels au nombre d'étages qui restent à tester pourrait donner raison à Bellman et k-lys n'en serait pas très éloigné.
Bon, c'était juste pour relancer le débat...
A+

Hors ligne

#13 14-06-2007 09:52:00

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Bonjour,
Oui, c'est vrai, pour que chacun puisse tester sa solution j'aurais dû donner la formule d'espérance.
Donc tjs sauf erreur :
E = {n² + Somme (k=1..n) [p(k)]²}/200
où :
- E est le nombre moyen de tests ;
- p(k) est l'amplitude du k-ième pas ;
- n est le nombre de pas (ou tests) effectués avec la première boule.
Exemple
Stratégie à un seul pas
p(1) = 99
E = 49,01
A+

Bonjour désolé,
Inconvénient de ne pas disposer de suffisamment de temps pour résoudre un pb. en une seule fois :
- on y passe 4 fois plus de temps,
- et on donne de fausses espérances...
=======
Rectificatif
=======

E = {Somme (k=1..n) [p(k).(p(k) + k - 1)]}/200

Sauf nouvelle erreur évidemment. Grrr !!!!
A+

Dernière modification par john (15-06-2007 09:40:00)

Hors ligne

#14 16-06-2007 10:22:46

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Hello,

Voici venue l'heure de la réponse, et,  si l'espérance du nombre de tests est bien :
E = {Somme (k=1..n) [p(k).(p(k) + k - 1)]}/200
on obtient E = 6,93 pour k-lys (avec sa suite de 11 pas : 14, 13, 12... 5, 4).

L'optimisation de E aboutit à une vingtaine de pas, d'amplitudes non entières (ce qui est très gênant !).
La courbe E(n) étant très plate au voinage de n=20, je me suis contenté de prendre des pas arrondis aux plus proches entiers avec une contrainte de somme des pas de 99.
Ainsi, la suite de 18 pas {10, 9, 9, 8, 8,..., 2, 2, 1} avec une espérance de 6,33 me semble-t-elle bien placée. On doit pouvoir faire mieux (mais guère à mon avis !).

NB
En tous les cas, sauf ruse de résolution, ce pb. ne me semble pas du niveau d'un test d'embauche ou d'un QCM !
Fred, pourrais-tu donner aussi la solution µsoft ?
A+

Hors ligne

#15 16-06-2007 20:13:19

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Enigme - Embauche chez Microsoft

Salut,

  Evidemment, le problème posé avec "en moyenne" au lieu de "au pire" est probablement très difficilement
soluble, sauf à faire une optimisation comme John l'a proposé.
  En revanche, si on écrit "au pire", ce qui était vraisemblablement le cas lors des test d'embauche,
c'est la réponse de k-lys qui est la meilleure!
Pour l'anecdote, chez microsoft, il proposait de prendre un pas de 10 constant...

Fred.

Hors ligne

#16 17-06-2007 23:18:59

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Hello,
Juste un peu frustré par la réponse de Fred car il s'agissait bien de déterminer une stratégie permettant d'effectuer EN MOYENNE un minimum d'essais :

Fred a écrit :

Quelle est la stratégie optimale pour effectuer, en moyenne, le moins de lancers
possibles (sachant bien sûr que l'on ne dispose que de deux boules...
Fred.

Mais le pire, c'est finalement de ne pas avoir la réponse exacte car la solution que j'ai proposée peut être fausse (ce ne serait hélas pas la première fois).
A+

Modif. ce matin.
Hier soir, j'avais un doute en lisant la réponse proposée par Fred et effectivement, je me suis encore planté dans le calcul de l'espérance. Donc, suivant les conseils du sage :

"Vingt fois sur le métier remettez votre ouvrage ; Polissez-le sans cesse et le repolissez."

je vais tout refaire proprement avant d'en faire part. Si la réponse de k-lys est la bonne, je dois la retrouver. Grands bravos à k-lys en tous les cas car quel raccourci par rapport à la méthode d'optimisation classique !
A suivre...

Dernière modification par john (18-06-2007 10:02:58)

Hors ligne

#17 20-06-2007 14:39:59

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Hello tous & toutes,

Voici en plusieurs parties, expliquées, revues et corrigées, ma dernière proposition...

Notations
-----------
n    nombre total de pas (c-à-d. d'essais avec la boule 1) dans toute la stratégie
    (exemple : les 11 pas de la stratégie de k-lys)

p(i)    nombre d'étages du i-ème pas de la stratégie
    (un pas de 13 permet de passer du 14-ième au 27-ième étage)
   
Hypothèse d'équiprobabilité
--------------------------------

On considère l'événement Ek : "Les boules cassent à partir de l'étage k".
La probabilité de Ek est supposée indépendante de l'étage et on a :

    Pr(Ek) = 1/100

Espérance du nombre d'essais
-----------------------------------

    1) Essais avec la boule 1
La probabilité P1(i), de casser la boule 1 au i-ème essai, est la probabilité que les boules cassent à partir de l'un des étages du i-ème pas. Soit, avec l'hypothèse d'équiprobabilité  :
    P1(i) = p(i)/100
On en déduit l'espérance E1, du nombre d'essais avec la boule 1 :
   
    E1 = Somme (i=1..n) i*p(i)/100

    2) Essais avec la boule 2
Sachant que la boule 1 s'est cassée au i-ème essai, l'hypothèse d'équiprobabilité permet de calculer E2(i), le nombre moyen d'essais à effectuer dans le i-ème pas avec la boule 2 :
    E2(i) = [p(i) - 1]/2
On en déduit l'espérance E2, du nombre d'essais avec la boule 2 :
   
    E2 = Somme (i=1..n) E2(i)*p(i)/100 = Somme (i=1..n) [p(i) - 1]*p(i)/200

L'espérance E du nombre d'essais avec les boules 1 et 2 s'écrit donc :
   
    E = E1 + E2 = Somme (i=1..n) [p(i) + 2*i - 1]*p(i)/200

[ndlr : J'espère que vous lirez la suite... bien que je me sois planté 2 fois dans mes messages précédents simplement en additionnant E1 et E2]
   
Dernier essai avec la boule 1
---------------------------------

Dans le pire des cas, les boules cassent à partir du 100-ième étage. La stratégie à adopter doit donc s'achever par un essai de la boule 1, effectué depuis le 99-ième étage.
On en déduit une relation sur la somme des pas :

    Somme (i=1..n) p(i) = 99

(à suivre...)

Hors ligne

#18 20-06-2007 19:12:44

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

[ndlr : Un peu difficile à digérer sans avoir eu les cours correspondants mais bon exemple d'application.]

Optimisation du nombre d'essais
-------------------------------------

Le problème est de définir une suite finie {p(i), i=1..n} de pas entiers et de somme 99, qui rende l'espérance E minimum. Noter que n, le nombre de pas, n'est pas imposé.

Pour résoudre ce pb., on considère le point P de composantes p(i), i=1..n dans un espace de dimension n et la fonction scalaire E(P) à minimiser avec une contrainte de somme des composantes de P de 99.

1) En différentiant E au voisinage de son minimum (sous réserve d'existence), on doit avoir :
    dE(P) = grad(E).dP = 0
[ndlr : ici, pas de panique avec le gradient, ce n'est qu'une notation bien pratique lorsque la fonction a plus d'une variable... voir le calcul du gradient dans ce qui va suivre.]
Cette relation peut s'interpréter comme le produit scalaire du vecteur  "gradient de E par rapport à P" et d'un vecteur "petit déplacement de P". Ce produit scalaire étant nul, on peut dire que la variation de E au voisinage de P est pratiquement nulle si le déplacement dP de P est orthogonal au vecteur grad(E).

2) Par ailleurs, en différentiant la somme des pas, on a :
    Somme (i=1..n) dp(i) = 0
Or cette somme s'interprète aussi comme le produit scalaire de dP et d'un vecteur U de dimension n et de composantes (1, 1 ..1).
[ndlr : En dimension 3, ce vecteur U serait porté par la diagonale principale du repère.]
Cette relation s'écrit donc ainsi :
    U.dP = 0
Elle indique également que U est un vecteur orthogonal à dP. On en déduit immédiatement une solution du problème posé :

    grad(E) = K.U    (avec K = constante).

Calcul de la suite de pas
----------------------------

Les composantes du gradient sont obtenues en dérivant E(P) successivement par rapport aux p(i), ce qui conduit aux n relations :

    2.p(i) + 2.i - 1 = 200.K    (pour i=1..n)

La somme de ces égalités permet de relier K au nombre n de pas :

    198 + n² = 200.n.K

En éliminant K,  on obtient une suite de pas en fonction de n :

    p(i) = 99/n + (n+1)/2 - i    (pour i=1..n)

La suite est une discussion de cette solution.

A+

Hors ligne

#19 20-06-2007 23:03:33

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

[ndlr : les calculs sont "presque" terminés mais il reste à interpréter...]

Discussion
------------

1/ Pour n = 9 ou 11, les pas minimisant E(P) sont entiers et on retrouve la stratégie à 11 pas (14, 13, 12, 11,  10, 9, 8, 7, 6, 5, 4) proposée par k-lys. Le nombre moyen d'essais (espérance E) est alors de 9,35.
[ndlr : SUPER !!! c'était mon objectif, car je n'ai pas vraiment percuté sur la démo. de k-lys. Faudrait bien qu'il détaille un peu...]

2/ Les pas p(i), d'amplitude décroissante, doivent être positifs, et en particulier le dernier : p(n). L'inégalité p(n) > 0  implique :

    198 > n.(n-1) => n = 14 au plus

3/ Avec cette restriction, tout nombre de pas n imposé , conduit à une stratégie optimale. Par exemple, la suite (15, 14, 13, 12, 11, 10, 9, 8, 7) est une stratégie optimale à 9 pas. Son espérance est de 9,6.

4/ Le calcul de l'espérance en fonction de n donne :

    E(n) = [99²/n + 1189.n/12 - n^3/12]/200

Dans l'intervalle utile [1..14], E(n) passe par un minimum en n* # 13,78, malheureusement non entier.
Ceci signifie que E* = 9,29 (espérance de ce minimum ) ne peut être atteinte en pratique avec des pas entiers.

5/ Cependant, il n'est pas exclu qu'une stratégie à 13 ou 14 pas entiers de somme 99 et d'espérance inférieure à 9,35 (k-lys) puisse exister. Vu le graphe de E(n), fonction décroissante jusqu'à n*, on recherchera une startégie à 14 pas entiers plutôt qu'à 13.

6/ Et pour preuve qu'il existe une meilleure stratégie (puisqu'il suffit d'en trouver une...), la suite de 14 pas :

    (13, 13, 11, 11, 9, 9, 7, 7, 5, 5, 3, 3, 2, 1)

de somme 99 a une espérance de 9,31. Il en existe beaucoup d'autres et peut-être même de meilleures. Avis aux amateurs !

Bonne nuit.

Hors ligne

#20 21-06-2007 21:25:50

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : Enigme - Embauche chez Microsoft

Quel champion ce John!!!

Hors ligne

#21 21-06-2007 23:49:22

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Merci à yoshi... et Fred, aurais-je réussi à te convaincre ????
A+

Hors ligne

#22 22-06-2007 09:28:12

galdinx
Modo gentil
Inscription : 21-06-2006
Messages : 506
Site Web

Re : Enigme - Embauche chez Microsoft

Salut John,

Tu es embauché^^

++

Hors ligne

#23 22-06-2007 12:04:41

john
Membre actif
Inscription : 10-02-2007
Messages : 543

Re : Enigme - Embauche chez Microsoft

Hello galdinx,
... excellente nouvelle, mais, bien que j'aime travailler pour rien, la question est quand-même : "A combien ?"
A+

Hors ligne

#24 24-06-2007 16:30:07

galdinx
Modo gentil
Inscription : 21-06-2006
Messages : 506
Site Web

Re : Enigme - Embauche chez Microsoft

Hi

D'abord désolé de pas répondre vite mais j'avais pas d'internet depuis 2 jours, en principe je réponds vite.

john a écrit :

'A combien ?'

Pour ton embauche chez microsoft il faut voir avec Billou...

Après, si tu veux venir travailler sur Bibmath, sois rassuré, on ne te demandera pas de payer...

++

Hors ligne

Pied de page des forums