The Most Wonderful Prince

[bonanova]

The King has decreed that his daughter the Princess shall marry the most wonderful Prince in all the land. One hundred suitors have been selected from their written applications, and on a certain day the King arranges for them, in turn, to interview the Princess. Each suitor must either be chosen or eliminated on the spot. If the Princess does not choose any of them, she will marry the last Prince to speak with her.

You have been chosen as the Royal Advisor to the Princess and tasked with implementing her best strategy to choose the Most Wonderful Prince of the realm. You devise an evaluation scheme by which the princess can assign a unique "wonder number" to each prince as she meets him. The strategy then is to have the Princess reject, but record the highest score of, the first N princes that she meets. The Princess will then choose the first Prince that she subsequently interviews whose score exceeds that recorded score.

That's it. The puzzle is basically solved. Except, of course, to decide on the optimal value of N. It requires some thought. If N to too high, the most wonderful prince is likely to be eliminated at the outset, and she ends up with the last guy. If N is too small, the Princess will likely settle for a fairly undistinguished prince.

What value of N optimally balances these two risks? What is the probability that the Most Wonderful Prince will be chosen?

Disclaimer: I recall this puzzle being posted before, with different flavor text. And it's somewhat of a classic. To give it a fair play here, I'll ask not to post any links and not to just give the answer if you know it, at least not without "showing your work."

[plasmid]

  Reveal hidden contents

It sure looks like 1/e, but when I try taking the derivative of that formula I had earlier and setting it to zero, it turns into a mess. FWIW, I'm getting the following:

My estimate was
Sum_{[GCD=2 to K]} N(K-N)^GCD-1 / (GCD-1)K^GCD

We’re trying to find the value of N that makes that function maximal, so take the derivative and find out where it’s zero.

d/dN = 
Sum_{[GCD=2 to K]} d/dN [N(K-N)^GCD-1 / (GCD-1)K^GCD] =

Sum_{[GCD=2 to K]} d/dN [N(K-N)^GCD-1] / (GCD-1)K^GCD

Using the product rule [(fg)’ = f’g + fg’] where f(N) = N, f’(N) = 1, g(N) = (K-N)^GCD-1, g’(N) = 
substitute u = K-N, du/dN = -1
d (K-N)^GCD-1 / dN
= d u^GCD-1 / du x du/dN
= -(GCD-1) u^GCD-2
= -(GCD-1) (K-N)^GCD-2

So we have
Sum_{[GCD=2 to K]} [(K-N)^GCD-1 – N(GCD-1)(K-N)^GCD-2] / (GCD-1)K^GCD

Sum_{[GCD=2 to K]} (K-N)^GCD-2 [(K-N) – N(GCD-1)] / (GCD-1)K^GCD

And that's as far as i got before I flipped a table.

(╯°□°）╯︵ ┻━┻

 

[plasmid]

  On 4/4/2018 at 2:34 AM, plasmid said:

This is a start but not a complete answer.

If you care only about whether the Princess picks the Most Wonderful Prince, and don’t care whether a failed attempt gets her the second best guy or the village donkey because you consider anything less than the best to be a loss:

  Reveal hidden contents

Call the highest ranking guy among the first N the Greatest Chump Dude (GCD, not to be confused with greatest common denominator). The odds that the GCD is the Most Wonderful Prince (MWP, rank #1) is simply the odds that MWP is within the first group of N, so
    P(GCD = #1) = N/100
The odds that the GCD is the second highest ranking suitor is the product of (the odds that GCD is not MWP) x (the odds that the second ranking guy is within the first N suitors if you’re given that GCD is not MWP), so
    P(GCD=2) = [(100-N)/100] x (N/99)
By similar logic, the odds that the GCD is the third ranking suitor is
    P(GCD=3) = [(100-N)/100] x [(99-N)/99] x (N/98)
Et. cetera.

If you know the rank of GCD (and if GCD is not MWP) then you know the Princess will pick the first suitor that outranks GCD, so the odds that she picks MWP will be [1/(GCD-1)].

So the odds that both (GCD is the second best suitor) and (she picks MWP if you’re given that GCD was the second best suitor) are
    P(GCD=2) x [1/(GCD-1)]
    [(100-N)/100] x (N/99) x [1/(2-1)]
    [(100-N)/100] x (N/99)
And the odds that both (GCD is the third best suitor) and (she picks MWP if you’re given that GCD was the third best suitor) are
    P(GCD=3) x [1/(GCD-1)]
    [(100-N)/100] x [(99-N)/99] x (N/98) x [1/(3-1)]
    [(100-N)/100] x [(99-N)/99] x (N/98) x [1/2]

And the overall odds that she picks MWP are the sum of all of those (odds that GCD is rank M) x (odds that she picks MWP if you’re given that GCD was rank M) terms for M=2 to 100. That ends up being a function of N, but it’s a function that’s too complex to solve without resorting to a computer unless you can simplify it.

 

Expand  

I’m going to make the math easier by

  Reveal hidden contents

not assuming that there are 100 suitors, but assuming there are a “large” number of suitors. Let’s say it’s the whole kingdom, K, so modifying my previous answer accordingly we have:

P(GCD=1) = N/K
P(GCD=2) = (K-N)/K x N/(K-1) ~= (K-N)/K x N/K = N(K-N) / K²
P(GCD=3) = (K-N)/K x (K-N-1)/(K-1) x N/(K-2) ~= [(K-N)/K]² x N/K = N(K-N)² / K³
P(GDC=X) ~= N(K-N)^X-1 / K^X

And the odds of picking MWP for any given GCD are still 1/(GCD-1) so the odds of picking MWP are approximately

Sum_{[GCD=2 to K]} N(K-N)^GCD-1 / (GCD-1)K^GCD

That doesn’t make it easy enough to just calculate by hand, but it does make it easy enough to make a spreadsheet to handle the calculations. If I make K=100, then this estimate says that the best number of chumps is 37 of the hundred, which would leave (ironically?) about a 37% chance of getting the MWP.

 

[plasmid]

This is a start but not a complete answer.

If you care only about whether the Princess picks the Most Wonderful Prince, and don’t care whether a failed attempt gets her the second best guy or the village donkey because you consider anything less than the best to be a loss:

  Reveal hidden contents

Call the highest ranking guy among the first N the Greatest Chump Dude (GCD, not to be confused with greatest common denominator). The odds that the GCD is the Most Wonderful Prince (MWP, rank #1) is simply the odds that MWP is within the first group of N, so
    P(GCD = #1) = N/100
The odds that the GCD is the second highest ranking suitor is the product of (the odds that GCD is not MWP) x (the odds that the second ranking guy is within the first N suitors if you’re given that GCD is not MWP), so
    P(GCD=2) = [(100-N)/100] x (N/99)
By similar logic, the odds that the GCD is the third ranking suitor is
    P(GCD=3) = [(100-N)/100] x [(99-N)/99] x (N/98)
Et. cetera.

If you know the rank of GCD (and if GCD is not MWP) then you know the Princess will pick the first suitor that outranks GCD, so the odds that she picks MWP will be [1/(GCD-1)].

So the odds that both (GCD is the second best suitor) and (she picks MWP if you’re given that GCD was the second best suitor) are
    P(GCD=2) x [1/(GCD-1)]
    [(100-N)/100] x (N/99) x [1/(2-1)]
    [(100-N)/100] x (N/99)
And the odds that both (GCD is the third best suitor) and (she picks MWP if you’re given that GCD was the third best suitor) are
    P(GCD=3) x [1/(GCD-1)]
    [(100-N)/100] x [(99-N)/99] x (N/98) x [1/(3-1)]
    [(100-N)/100] x [(99-N)/99] x (N/98) x [1/2]

And the overall odds that she picks MWP are the sum of all of those (odds that GCD is rank M) x (odds that she picks MWP if you’re given that GCD was rank M) terms for M=2 to 100. That ends up being a function of N, but it’s a function that’s too complex to solve without resorting to a computer unless you can simplify it.

 

[bonanova]

  On 4/7/2018 at 2:21 AM, plasmid said:

I’m going to make the math easier by

  Reveal hidden contents

not assuming that there are 100 suitors, but assuming there are a “large” number of suitors. Let’s say it’s the whole kingdom, K, so modifying my previous answer accordingly we have:

P(GCD=1) = N/K
P(GCD=2) = (K-N)/K x N/(K-1) ~= (K-N)/K x N/K = N(K-N) / K²
P(GCD=3) = (K-N)/K x (K-N-1)/(K-1) x N/(K-2) ~= [(K-N)/K]² x N/K = N(K-N)² / K³
P(GDC=X) ~= N(K-N)^X-1 / K^X

And the odds of picking MWP for any given GCD are still 1/(GCD-1) so the odds of picking MWP are approximately

Sum_{[GCD=2 to K]} N(K-N)^GCD-1 / (GCD-1)K^GCD

That doesn’t make it easy enough to just calculate by hand, but it does make it easy enough to make a spreadsheet to handle the calculations. If I make K=100, then this estimate says that the best number of chumps is 37 of the hundred, which would leave (ironically?) about a 37% chance of getting the MWP.

 

Expand  

Great job! Want to look at the reciprocal of that number and guess the exact result?

[bonanova]

@plasmid Not sure why derivative failed, but you're right about the result. Nice solve.

  Reveal hidden contents

It's exact for infinitely many princes, otherwise stop at the floor function of N/e.

 

[plasmid]

Is there an easier way to reach the solution? If I try to handle the case of an infinite number of princes to choose from, and I deal with the exact formula I was working with initially instead of the simplified approximation that I ended up using to be able to actually calculate an answer, then I get

  Reveal hidden contents

Then you get to take the derivative of that with respect to N, set it to zero, and find the limit as K goes to infinity. Which will involve converting factorials to gamma functions so you can take the derivative. And will most definitely lead to more table flipping.

 

[bonanova]

  On 4/11/2018 at 5:14 AM, plasmid said:

Is there an easier way to reach the solution? If I try to handle the case of an infinite number of princes to choose from, and I deal with the exact formula I was working with initially instead of the simplified approximation that I ended up using to be able to actually calculate an answer, then I get

  Reveal hidden contents

Then you get to take the derivative of that with respect to N, set it to zero, and find the limit as K goes to infinity. Which will involve converting factorials to gamma functions so you can take the derivative. And will most definitely lead to more table flipping.

 

Expand  

So this guy Thomas Bruss solved the general stopping problem.

  Reveal hidden contents

(Check out section 2 on page 1388 of the pdf file available in the above link.)

Bruss assigns 1 or 0 to each event in case it's a best case so far. Then the problem reduces to finding the final 1 in the sequence. The probability p_k of say the k^th event being a 1 is 1/k, making the odds r_k = p_k/(1-p_k) = 1/(k-1). He then summed the odds starting with the last event and working backward, stopping when that sum first reaches (or exceeds) unity: (Edit): R_s = 1/(n-1) + 1/(n-2) + ... + 1/(s-1) >=1. He proved that s is the optimal stopping point. And doing the math he showed that s/n = 1/e and that ((s-1)/n)R_s (the probability of success) approaches 1/e, as well as n -> infinity.

It's really a beautiful result.

 

Edited April 15, 2018 by bonanova
corrected Rs formula