Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/26/83; site ihuxr.UUCP
Path: utzoo!linus!decvax!harpo!floyd!vax135!ariel!hou5f!orion!houca!hogpc!houxm!hocda!spanky!burl!sb1!ll1!otuxa!we13!ihnp4!ihuxr!lew
From: lew@ihuxr.UUCP
Newsgroups: net.math
Subject: Answer to Silvio Levy's puzzle
Message-ID: <586@ihuxr.UUCP>
Date: Sat, 27-Aug-83 16:46:58 EDT
Article-I.D.: ihuxr.586
Posted: Sat Aug 27 16:46:58 1983
Date-Received: Tue, 30-Aug-83 01:38:30 EDT
Organization: BTL Naperville, Il.
Lines: 18

I sent Silvio Levy mail on this but I guess it didn't go through. So, for
the record, Leo Ringwald and I independently came up with the answer that the
probability of a strategy M succeeding, where strategy M is to "stick" on
the highest number after drawing M numbers, is:

	P(M,N) = 1/N * sum i = M, N-1 of 1/i

As N gets large the optimal M approaches N/e and P(M,N) -> 1/e.

Leo's derivation of P(M,N) was nice and simple. He reasoned that there is
a probability 1/N of the highest number being drawn on the ith turn. With
i > M, there is a probability M/i-1 of the highest of the first i-1
numbers being drawn in the first M. The above formula follows immediately
(with a change of dummy variable.)

For N=10, the best M is 3 with a probability .398690 of succeeding.

	Lew Mammel, Jr. ihuxr!lew