Author |
Topic: The sultan and his 100 wives (Read 9812 times) |
|
Thordain
Newbie
Posts: 3
|
 |
The sultan and his 100 wives
« on: Jul 23rd, 2003, 3:03am » |
 Quote  Modify
|
Here is a pretty tough riddle. It requires basic knowledge of combinatorics (at least it did for me). I haven't seen it on the riddles page so I thought I'd post it here for inclusion. Apologies if its already on the site!
The sultan has gathered the 100 most beautiful women in the kingdom. He is to pick one of them as his wife. Each woman has a beauty ranking, such as #2, or #29. Each woman appears before the sultan once, and then the sultan can either choose her or reject her. Once he rejects a woman he can never choose her again. If he has not chosen a woman by the 100th candidate, he must choose her. The women are shown to the sultan in random order. What is the sultan's best strategy for choosing his wife?
I've never seen an official answer to this problem, but I'd sure like to check if my solution matches with what someone else got  . Don't want to spoil anything offhand so I'll only post my solution if asked
//"New Problem" removed from title by moderator //
|
| « Last Edit: Aug 28th, 2003, 6:16pm by Icarus » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: A new problem: The sultan and his 100 wives
« Reply #1 on: Jul 23rd, 2003, 3:43am » |
Quote Modify
|
This riddle comes in many guises, one of which is on the site I think. You can easily find the answer by simulating it, the math to the exact answer is a bit more problematic (espescially for the general case of N wives to choose from, rather than 100)
It's interesting to see that the strategy for getting the highest chance of the best wive, doesn't have the best average expected value (given a uniform, or normal distribution of wive-values)
Also when you know more about the distribution of the group (for instance that it is a normal distribution) you can get a better chance at finding the best.
The official answer for the general case is 1/e ~= 37% chance of finding the best when choosing the first one better than the best from the first 1/e part of the prospects .
the problem is also known as 'dowry problem', 'googol', secretary problem' and 'beauty contest problem'.
If you want the math, the whole math and nothing but the math I suggest looking up
Ferguson, T.S. (1989), "Who solved the secretary problem?", statistical science, 4, p. 282-296
and
Gilbert, J. P. & Mosteller F. (1966), "Recognizing the maximum of a sequence", American statistical Association Journal, 61, p. 36-73
But frankly I got a headache just looking at it..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Thordain
Newbie
Posts: 3
|
|
Re: A new problem: The sultan and his 100 wives
« Reply #3 on: Jul 23rd, 2003, 12:59pm » |
Quote Modify
|
Ok, here is what I got:
Ok, here is the solution I got.
In general: For N women, and a discarding the first k, the expected rating of the date is what?
If the most beautiful woman is in the first k, then willy ends up discarding all other women and is stuck with the last one, with an expected rating of (1 + N - 1)/2
. The chance of this happening is k/N. So the expected return in this case is
N/2 * k/N = k/2
If the most beautiful woman is NOT in the first k, then willy will get the first woman more beautiful than the best of the first k. If the most beautiful woman of the first k has a rating of p, then willy's woman will get an expected rating of (p + 1 + N)/2. The chance of this happening is (N-k)/N. So the expected return in this case is
(p+1+N)/2 * (N-k)/N
The calculation of p is a little trick and takes some combinatorial identities to reduce. But I eventually found that
p = N - (N - k)/(k + 1)
After some algebra to clean this up, we get.
E(k, N) = N - k/2 - (N-k)(N-k-1)/2N(k+1)
For the case of 100, in the sultan and his 100 wives problem
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1058954585
I plugged in values for N 100 and k ranging for 1 to 11, and found that it maxes out at k = 9, with
E(9, 100) = 91.405
So by discarding the first 9 women out of 100, willy can get an expected rating of 91.405.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A new problem: The sultan and his 100 wives
« Reply #4 on: Jul 23rd, 2003, 2:04pm » |
Quote Modify
|
From the literature I get a slightly higher average rating (since it's rounded to 92%, so must be over 91.5%), but it's still at k=9.
The question is, does it solve the problem? Are we trying to maximize chances of getting the best bride, or maximizing the expected value.
And you could also aim for maximizing the chance of getting a bride from the top 10 percentile, or top 25 percentile, or minimize the chance of getting one from the bottom 10 or 25 percentile.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: A new problem: The sultan and his 100 wives
« Reply #5 on: Jul 24th, 2003, 11:14pm » |
Quote Modify
|
Thordain, you do not describe your method or what you mean by best strategy. To make this problem different from the Bachelors Dilemma thread, I will assume best strategy means to maximize expectation. For your strategy, it looks like you might mean "Pass up, but observe the first k candidates. Then take the first one better than the best one of the first k." This is not the best strategy. A simple modification can improve upon it (at least for N=100, and k=9): If there are only two women left and the 2nd to last one is better than the median woman of those observed so far, select her. Otherwise select the last one.
This problem is fairly easy to simulate by a program to try various strategies. I tried this for N = number of women = 100, and the following worked well:
Observe the first 20 women and rank them in order. Take the first woman better than the best of the first 20 until woman number 58. If nobody better has come along by number 58, then time to lower your standards and take the first one better than the third best from among the first 20. Do the same thing for the last two women as suggested above. Expectation: 96.1.
Looks like there are lots of ways to make small improvements. With a slightly more complex approach I get an expectation of 96.6.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A new problem: The sultan and his 100 wives
« Reply #6 on: Jul 25th, 2003, 12:42am » |
Quote Modify
|
I think you could also make a probability distribution, and use that. Chances are you're dealing with a normal distribution, but even if it's something completely different you'll get an extra advantage.
I think you should continually adjust you're aspiration level to maximize the expected utility.. And the more you know about the probability distribution the better your chances.
|
| « Last Edit: Jul 25th, 2003, 12:46am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print