<HTML>
<HEAD>
   <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
   <META NAME="Author" CONTENT="Claus Michael Ringel">
   <META NAME="Keywords" CONTENT="">
<TITLE>Permutations: 37 percent rules</TITLE>
  <link rel="stylesheet" type="text/css" href="vortrag.css">
</HEAD>
<body LINK="blue" VLINK="black" ALINK="red">
<p>
<b>The secretary problem: </b>
A company is looking for a secretary. 
<br>n people apply, they are interviewed one after the other.
<br>One can compare anyone only with the previously seen applicants. 
<br>Whoever is not chosen direcftly after the interview, is rejected for ever. 
<br>
<br>
The strategy:
<br>(odds-strategy, stop-index-strategy, Bruss-strategy):
<br>
<br>Wait for a while, say until after interview number s (the "stop index").
<br>Then choose the first one who is better then all the previous ones
<br>(or else the last one). 
<br>
<br>
What is optimal?
<table><tr><td bgcolor=yellow>
<p>Optimal is &nbsp; s = 1/e &approx; 37 %.
</table>
<br>
Again a 37% rule!
<p>
For the proof, one has to look also here at all permutations of n.
<p>


</body>
</html>