This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

Sultan's Dowry

A sultan has granted a commoner a chance to marry one of his hundred

daughters. The commoner will be presented the daughters one at a time.

When a daughter is presented, the commoner will be told the daughter's

dowry. The commoner has only one chance to accept or reject each

daughter; he cannot return to a previously rejected daughter.

The sultan's catch is that the commoner may only marry the daughter with

the highest dowry. What is the commoner's best strategy assuming

he knows nothing about the distribution of dowries?

decision/dowry.s

Solution

Since the commoner knows nothing about the distribution of the dowries,

the best strategy is to wait until a certain number of daughters have

been presented then pick the highest dowry thereafter. The exact number to

skip is determined by the condition that the odds that the highest dowry

has already been seen is just greater than the odds that it remains to be

seen AND THAT IF IT IS SEEN IT WILL BE PICKED. This amounts to finding the

smallest x such that:

x/n > x/n * (1/(x+1) + ... + 1/(n-1)).

Working out the math for n=100 and calculating the probability gives:

The commoner should wait until he has seen 37 of the daughters,

then pick the first daughter with a dowry that is bigger than any

preceding dowry. With this strategy, his odds of choosing the daughter

with the highest dowry are surprisingly high: about 37%.

(cf. F. Mosteller, "Fifty Challenging Problems in Probability with Solutions",

Addison-Wesley, 1965, #47; "Mathematical Plums", edited by Ross Honsberger,

pp. 104-110)

Here's a twist on the sultan's dowry problem I hope hasn't been posted yet.

I became interested in an iterated version of this problem, which goes as

follows:

There's a long line of suitors outside the sultan's palace, and one by one

they come in. If a suitor gets the right girl, he marries her, as before.

Unfortunately (for the suitor, at least), if he doesn't, he gets his head

lopped off, and the next suitor comes in.

Anyway, the first few dozen guys all know their probability theory, so they

know that the best strategy is to skip the first 37 girls, and then pick

the first girl who is the best up to that point. Alas, each one assumes

that he's the only one who knows that strategy, so one by one, these few

dozen guys get their heads lopped off.

After the 49th head has just rolled down the hill, and the sultan's vizier

has just cried out, "Next!" the next guy in line says, "This isn't working

out. We might all be doing the same thing. It doesn't hurt any of us to

tell the rest what strategy we'll be using, so that none of us sets out to

pick the same girl over and over again. I might as well just tell you,

though, that I'm going to get her! I know this great strategy where you

skip the first 37 blah blah blah..." Naturally, a few moments later, head

number 50 comes rolling down.

"Next!" cries the vizier.

Well, suitor number 51 is in a quandary. He's all set to skip 37, etc, etc,

except now he knows, that's not the right strategy. But he doesn't know if

the last guy skipped the right girl because she was in the first 37, or if

he didn't meet her yet because he stopped too early.

QUESTION 1: What is his best strategy?

ANSWER 1: His best strategy is:

"Skip the first 14. Take the first girl in [15,37] who is better

than the first 14. If there isn't one, take the SECOND girl in [38,100]

who is the best up to that point."

Unfortunately, head number 51 rolls down the hill. "Next!" cries the vizier,

who is getting a little hoarse, and wishes he didn't have this job.

QUESTION 2: What is suitor number 52's best strategy?

ANSWER 2: His best strategy is:

"Skip the first 5. Take the first girl in [6,14] who is better than

the first 5. If there isn't one, take the SECOND girl in [15,37]

who is the best up to that point. If there isn't one, take the THIRD

girl in [38,100] who is the best up to that point."

By the end of the day, of course, a wedding will be set, won't it?

MORE QUESTIONS: If each suitor uses the best strategy at that point, how

many suitors will it take before the right girl is certain to be found?

Does each succeeding suitor always have a better chance of winning

than the preceding one?

SPECULATION: The last strategy is "Pick the last girl." Its probability

of success is 1. And it is strategy number 100. (The corresponding

conditions hold for 3, 4, and 5 daughters.)

Does anyone have any observations on this one?

byron elbows

(mail to brian@cs.ucla.edu)

Continue to: