## 100 Princesses Problem... and dating

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

### 100 Princesses Problem... and dating

Surely you've heard of the 100 princesses problem.

You're an eligible prince, and your dad (the king) has arranged for you to marry one of 100 available princesses. You want a good one, of course. The princesses are summoned and lined up. You're allowed to meet with each one in turn (not knowing what the rest look like/act like/etc.), and are allowed to either accept or reject. Once you reject a princess, you can't go back to her. Once you accept a princess, your decision is final. What strategy should you use to optimize your final choice?

It's a well-known problem (with considerable variation on theme).

My variation:

You're single and want a relationship. Your code of ethics prevents you from getting back with an ex. Assuming the pool of potential partners is larger than you'd be able to meet in your lifetime, what strategy should you adopt to find the love of your life?

4=5
Posts: 2073
Joined: Sat Apr 28, 2007 3:02 am UTC

### Re: 100 Princesses Problem... and dating

have you tried joining clubs that do things you enjoy? Or maybe starting one. Try going to street fairs and other public gatherings. Ask your friends to keep an eye out for someone that would suit you. Or you could do what I did and knit in public. Have you tried putting a math problem on the board that when solved gives your phone number?

Turtlewing
Posts: 236
Joined: Tue Nov 03, 2009 5:22 pm UTC

### Re: 100 Princesses Problem... and dating

Well i suppose:
Spoiler:
get first partner
While (current partner != "love of your life") get another partner

I think the real question here is "how do you know when you've found the love of your life?"

Another
Posts: 25
Joined: Mon Sep 29, 2008 11:08 am UTC
Location: GMT+3

### Re: 100 Princesses Problem... and dating

Turtlewing wrote:Well i suppose:
Spoiler:
get first partner
While (current partner != "love of your life") get another partner

I think the real question here is "how do you know when you've found the love of your life?"

I think that is a self-solving question. When you have found - you know, if you are not sure - you haven't found.

To slightly modify the pseudocode:
Spoiler:
while( !sure(current_potential_partner == "love of your life")) search_for_partner(this->life);

Of course that is based on the assumption of "you know when you have found" which may be wrong. However that is probably the simplest assumption that is required for a solution to exist at all. Since the practical interest is probably in a solution, not in the problem, adding assumptions to the under-defined starting conditions is reasonable.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Re: 100 Princesses Problem... and dating

My take on it is this:
Spoiler:
For the 100 princesses problem, your best strategy is to reject the first 37 (calculated by N/e, where N=100), then accept the first princess that has the best suitability up to that point.

Assume you meet partners at a relatively constant rate. Determine an age at which you would like to have settled down with an ideal partner, and subtract the current date to set a time limit, rather than a partner limit. Start meeting/dating people rejecting those you meet until you reach 37% of your time limit. From there, continue meeting people until you've found one that bests the rejected group.

bengeance
Posts: 9
Joined: Sun Jul 13, 2008 10:34 pm UTC
Location: School Medford/Somerville, break Worcester MA
Contact:

### Re: 100 Princesses Problem... and dating

My take on it is this:
Spoiler:
For the 100 princesses problem, your best strategy is to reject the first 37 (calculated by N/e, where N=100), then accept the first princess that has the best suitability up to that point.

Assume you meet partners at a relatively constant rate. Determine an age at which you would like to have settled down with an ideal partner, and subtract the current date to set a time limit, rather than a partner limit. Start meeting/dating people rejecting those you meet until you reach 37% of your time limit. From there, continue meeting people until you've found one that bests the rejected group.

Will that solution to the 100 Princesses give the highest average quality or the highest percent of best quality brides? Also, could you link me to an explanation of why this is the solution or show me where to point my google stick? I've been wondering about the calculation since I saw a similar problem a while ago.

Thanks =)
"Maturity is the ability to pretend you are not immature" - my grandfather

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: 100 Princesses Problem... and dating

You only have to spoiler something if it contains an answer or a significant answer fragment.

I think that particular scheme must maximize the probability of finding the absolute best, but I think its pretty clear that it doesn't maximise the expected rank of the princess in question (think about what you should do if you are dating the second last princess and she's pretty high ranking out of the 99 that you've seen).

I'm pretty sure that this is a repeat but I don't recall the context that it was initially introduced with, and anyway it settled on the solution that redrogue has already produced iirc. It might be interesting to pursue the "maximise expected value" interpretation.

Purely as an aside regarding the initial presentation, I think its pretty ridiculous to believe that people can be put in a linear order. The various qualities that you value are rarely able to be precisely determined and summed. I also think the "love of your life" concept is deeply flawed. We live long lives, we find different qualities more or less attractive at different times.

So anyway, less of the sexist presentations and more of the precise specification of what the goal is please (though I quite like the recent trend towards working on generalisations of some of the more hackneyed puzzles).
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

### Re: 100 Princesses Problem... and dating

bengeance wrote:

My take on it is this:
Spoiler:
For the 100 princesses problem, your best strategy is to reject the first 37 (calculated by N/e, where N=100), then accept the first princess that has the best suitability up to that point.

Assume you meet partners at a relatively constant rate. Determine an age at which you would like to have settled down with an ideal partner, and subtract the current date to set a time limit, rather than a partner limit. Start meeting/dating people rejecting those you meet until you reach 37% of your time limit. From there, continue meeting people until you've found one that bests the rejected group.

Will that solution to the 100 Princesses give the highest average quality or the highest percent of best quality brides? Also, could you link me to an explanation of why this is the solution or show me where to point my google stick? I've been wondering about the calculation since I saw a similar problem a while ago.

Thanks =)

Same here... here's my attempt at the beginning of a solution:

Suppose there are N people in total and you decide to reject the first R, then pick the next one who is better than the first R (convince yourself that any strategy whose goal is to maximize the probability of getting the best person must be of this type). Note that it does not matter the order of the rankings of the first R people. For each 0 <= i <= N - R, we want the probability that there are exactly i people left who are better than the ones you chose. This happens when one person you chose is (i+1)th best, and everyone else you chose is picked from the bottom N - i - 1 people. So this probability is: $\binom{N-i-1}{R-1}/\binom{N}{R}$.

Now when this occurs, each of the i remaining people are equally likely to be picked, so the probability that you get the best one is 1/i. (In the case when i = 0, the probability is 0). So we get that the probability of getting the best person is:

$\binom{N}{R}^{-1}\sum_{i=1}^{N - R}\binom{N - i - 1}{R - 1}\frac{1}{i}$

Now ideally we can evaluate that expression?
Hey baby, I'm proving love at nth sight by induction and you're my base case.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Re: 100 Princesses Problem... and dating

The "Hundred Princesses Problem" is better known as the "Secretary Problem." The goal isn't highest average quality or highest percentage, but the single best candidate.

http://en.wikipedia.org/wiki/Secretary_problem

graatz
Posts: 87
Joined: Thu Oct 29, 2009 7:24 pm UTC

### Re: 100 Princesses Problem... and dating

Hm, I think I've applied to jobs where HR uses this kind of flawed policy. If I were the king, I would arrange them from best to worst just to be an ass about it. The longer you wait to decide, the worse off you'll be. Of course, the classic secretary problem assumes a random ordering, but the puzzle as stated here does not

I understand the basics of stopping problems, but they seem inherently flawed in real world situations. In this puzzle, for example, the prince simply must accept that while there may be a "perfect" bride in the 100, he should go through them only until he's found one he's happy with, and then stop. For the hiring a job candidate, hire the first person who meets your qualifications and interviews well, accepting that the real-world constraints of finding the "perfect" candidate are too cumbersome.