egs@ulysses.UUCP (08/28/83)
Regarding Silvio's problem. I think, but have not been able to prove yet, that the optimal strategy is of the form: let M numbers go by, and choose the first of the remaining numbers that is greater than the first M. What I get as the optimal value of M (if there are N numbers) is the value of M that maximizes the function: F(N,M) = 1/N * sum over k=M,N-1 of (M/k), (assign the ratio 0/0 the value of 1 to handle the case of M=0) which is a reduced form of: F(N,M) = 1/N! * sum over k=M,N-1 of (C(N-1,k)*M*(k-1)!*(N-1-k)!), which I get by counting the number of times the M-strategy picks the highest number and dividing by the total number of permutations. You can approximate F(N,M) as: F'(M,N) = M/N * (integral from M to N of 1/x dx) = M*(ln(N)-ln(M))/N. Finding the maximum value of F' with respect to M yields: max of F'(N,M) = 1/e at M = N/e, with the rather neat result that a fairly close approximation of the likelihood for guessing the highest number when following the optimal strategy is approximately 0.03679. As it turns out, for N=10, the best choice is M=3 with a 0.3987 chance of getting the highest number. For N=100, the best choice is M=37, with a 0.3710 chance. For N=1000, M=368, and chance is 0.3682. Ed Sheppard BTL @ MH