Keeper's keys issue

Let us imagine you work at night but you’ve just visited your friends and had a lot to drink. You stand in front of your workplace door and take out $n$ keys from your pocket and drop them on the floor. However, you don’t remember which key opens the door.
So you decide to try the first one you see. If it works, then good for you, but if it does not, you drop it on the ground in the middle of all the other keys. Of course, since you are drunk, you don’t remember where the key you just tried is. And you repeat the same process until you open the door.

What is the probability that it is the $k$ -th key which opens the door?

After spending the whole night trying to open the door, you decide to drink only tomato juice with your friends before going to work. You still don’t remember which key opens your workplace door but you now have a strategy and you put away any key you try that does not open the door.

In this new situation, what is again the probability that it is the $k$ -th key which opens the door?

I solved itMark it done Add to my listKeep it in your list

I like this problem2 likes

Liked by

Solutions

Reveal solutionsAre you sure? Give it a try first.

Solution by SequoiaFR

Discussions0 useful votes

Disons que la première clef n’ouvre pas la porte, elle fait donc parti des $n-1$ clefs qui n’ouvre pas la porte parmi les $n$ . Cette événement a donc une probabilité $\frac{n-1}{n}$ de survenir.
La seconde clef n’ouvre toujours pas la porte avec la même probabilité, ce qui rajoute un facteur $\frac{n-1}{n}$ . On itère ce raisonnement jusqu’à la $k-1$ -ème clef qui n’ouvre pas la porte. Tout cela est donc un événement de probabilité $\left(\frac{n-1}{n}\right)^{k-1}$ , où l’on peut tout multiplier par indépendance.
Mais la $k$ -ème clef va ouvrir la porte ! Ainsi cet événement a une probabilité $\frac{1}{n}$ d’advenir car on choisit une clef sur $n$ .
Finalement, la probabilité que la $k$ -ème clef ouvre la porte suit une loi géométrique de paramètre $\frac{1}{n}$ , le résultat est donc $\left(\frac{n-1}{n}\right)^{k-1}\,\frac{1}{n}$ .

2.La différence maintenant est que le gardien fait attention à la clef qu’il utilise. Disons que la première clef n’ouvre pas la porte, cela a donc une probabilité $\frac{n-1}{n}$ d’arriver, rien ne change pour l’instant.
Mais maintenant on met cette mauvaise clef de côté, il en reste donc $n-1$ . Si on en choisit une mauvaise, cela a une probabilité $\frac{n-2}{n-1}$ d’arriver ( $n-2$ mauvaises clefs dans les $n-1$ ).
Maintenant il reste donc $n-2$ clefs devant nous. On peut ainsi prolonger ce raisonnement jusqu’à ce qu’on ait tiré $k-1$ mauvaises clefs (donc il en reste $n-(k-1)=n-k+1$ ). On multiplie alors les probabilités pour trouver:
$\frac{n-1}{n}\frac{n-2}{n-1}\frac{n-3}{n-2}\cdots\frac{n-k+2}{n-k+3}\frac{n-k+1}{n-k+2}$ Mais on remarque que $n-1$ se simplifie, ainsi que $n-2$ , $n-3,\dots,$ jusqu’à $n-k+1$ qui, lui, va rester.
On trouve ainsi $\frac{n-k+1}{n}$ .
Mais maintenant il nous reste à tirer la bonne clef parmi les $n-k+1$ restante, événement de probabilité $\frac{1}{n-k+1}$ qui, multiplié par le résultat précédent, donne $\frac{1}{n}$ . Ainsi notre probabilité finale vaut $\frac{1}{n}$ . Elle ne dépend pas de $k$ !

Report