The Bachelor, first Impression rose

[NYplayer]

On ABC's the bachelor, he meets 25 women one at a time, and has a "first impression rose" to give to one of them upon meeting her. He is supposed to give it to the woman who makes the best first impression on him. However, he has to give it to her upon meeting her and without having yet met the remaining woman. So if he gives it to the second woman he meets and #10 turns out to be the one he likes most it's tough luck for him.

If after meeting them all he can rank them 1 through 25, what would be the best strategy for giving out a rose so that over the long run the woman who gets the rose has the lowest number (since #1 is the best). Assume the order he meets them in is random.
Keep in mind when he first meets someone he doesn't know her overall rank, that would make this trivially easy. He only knows her relative rank to the ones he has already met.

I thinik the solution will be something along the following lines. dont give a rose to women 1 through N and give a rose to the first woman after N who is better then all of 1 through N. Or the first woman after N who exceeds the average of 1-N.

For example. He should never give the rose to #1 because he has no idea how she will compare to the rest of the girls. It would also be a faulty to say I will not give a rose to 1 through 22 and give it to the first one after 22 who is better the all the ones I have seen. This wouldnt work because it is unlikey that 1,2, or 3 will be in the last 3 women.

So if you made 1 million ramdom sets of the numbers 1-25 and then were fed them one at a time and you knew how each new number compared to what you have seen but didnt' know where they fit in the whole order until you had seen everyone. what strategy would have you give the rose to lowest # (or best woman) on average?

[bigpooch]

This is commonly referred to as the "bachelor problem". A
useful link, is at:

http://www.mathpages.com/home/kmath018.htm

[jay_shark]

Here is a way to formalize the above problem .

We wish to show that the best strategy is to interview and reject k-1 bachelors and then select a bachelor from k, k+1,...n that is better than all of the previous bachelors . Let P(k) be the optimal probability given that all the previous candidates 1,2,3,...k-1 have been rejected .Also , the probability that any particular candidate is the best is 1/n .

If you reject candidate k , then P(k)=P(k+1) since you're rejecting 1,2,3,...k candidates . Moreover , we know that P(k)= 1/n + (k-1)/k*P(k+1) . This means that the probability that the kth candidate is the best is 1/n plus the probability that you reject the kth candidate (k-1)/k which you multiply by P(k+1) which is the probability that the best candidate will come from k+1, k+2, k+3 , ... n .

Therefore we have that P(k+1)> 1/n + (k-1)/k*P(k+1)

Solve for P(k+1) ; P(k+1)>=k/n

P(2)>=1/n
P(3)>=2/n
P(4)>=3/n etc

This is a starting point . Since we now know the optimal strategy for this game we can choose k to maximize the probability that we select the best candidate .

To be continued ....

[NYplayer]

[ QUOTE ]
This is commonly referred to as the "bachelor problem". A
useful link, is at:

http://www.mathpages.com/home/kmath018.htm

[/ QUOTE ]

this is actually differnt because in the problem you link to he "is concerned ONLY to maximize his chances of choosing the VERY best of the N candidates,placing no value at all on choosing the second-best versus the worst".

in your problem he can just keep searching. with my problem you will get no more than 25 candidates. and if you realize that you have passed up the woman who could have been best on the 3rd round, you still have to pick one to give the rose to. There for you should select the one you think has the best chance of being better than most.

[NYplayer]

OK, this isn't getting a lot of answers so instead of coming up with the optimal solution, how about what might be some things you might do in this situation?

i would pick the first one after #5 who was better than all of the first 5. if by #15 no one had surpassed someone in the first 5, i'd take anyone who seemed good. maybe anyone better than the average seen so far.

[Deveroast78]

He should have given it to Amanda... [img]/images/graemlins/smirk.gif[/img]

Personally I would have waited till the halfway point and hope the producers of the show "saved the best for last" limo, but the order of the women was probably determined randomly. Also, he had to take the women at face value at that point before knowing anything of their personalities. He happened to give it to a girl who showed some initiative by asking who the rose was for, as I recall, so kudos to her. In his shoes, I probably would have just given it to the cutest brunette.

[jay_shark]

Of all the solutions to this problem , I think the following is the simplest .

There are n bachelors and only two of them are relevant . The best bachelor and the second best bachelor . The best bachelor will be the kth bachelor and the second best bachelor will belong to the interval [1,k-1].

Let r be your final pick selection .

if k<r then you've rejected the best bachelor .
if k> r we get the following relevant partitions .
[1,r],(r,k], (k,n] . For your strategy to succeed , the second best bachelor in the interval [1,k-1]has to be in [1,r] otherwise he will be rejected before the best bachelor .

The probability of this happening is r/(k-1) given k >r .

Now we can write it using sigma summation notation summing over all the possible k choices . Using n=25 in your example .

P=1/25*[ r/(k-1) { k=r+1 to k=n}]
Now we've reduced the problem to a function of k which we can certainly maximize using derivatives and setting the derivative equal to zero .
The answer should be r=[25/e] =9 . Where [,] is the greatest integer less than or equal to x function .

[NYplayer]

[ QUOTE ]

Let r be your final pick selection .

r=[25/e] =9 .

[/ QUOTE ]

so? we should pick the 9th one? or just not pick someone in the first 9?

[jay_shark]

Yes I meant that you should choose the best bachelor available after you've rejected 9 of them .

[NYplayer]

if you dont see one better you just keep rejecting until you end up with #25 who you have to pick? or do you take one that would be better than any of the worst 7 or seomthing like that?