wu :: forums « wu :: forums - Bachelor's Dilemma » Welcome, Guest. Please Login or Register. Dec 16th, 2018, 8:41pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, towr, Grimbal, ThudnBlunder, william wu, SMQ, Icarus)    Bachelor's Dilemma « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Bachelor's Dilemma  (Read 13668 times)
Newbie

Gender:
Posts: 10
 Re: Bachelor's Dilemma   « Reply #25 on: Mar 26th, 2007, 12:13pm » Quote Modify

also known as the Sultan's Dowry Problem:

http://mathworld.wolfram.com/SultansDowryProblem.html
 IP Logged
titan
Newbie

Posts: 33
 Re: Bachelor's Dilemma   « Reply #26 on: Oct 15th, 2013, 1:39am » Quote Modify

"Willy should date some number k of the N, then marry the first one after number k that is better than all the previous women. Need to find k in terms of N that maximizes the probability of ending up with the best one.

The probability of ending up with the best of the N women with this strategy is:
p(date k+1 is best)
+ p(date k+2 is best)*p(best of the first k+1 was in the first k dates) "

1) Why shud Willy date some number k of the N, then marry the first one after number k that is better than all the previous women? Why shud this strategy be used? Why have this strategy been thought of?
2) This:p(best of the first k+1 was in the first k dates) is basically no. of ways in which best date is in 1-k/that in k+1 = kC1/(k+1)C1 = k/k+1
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: Bachelor's Dilemma   « Reply #27 on: Oct 15th, 2013, 7:16am » Quote Modify

on Oct 15th, 2013, 1:39am, titan wrote:
 1) Why shud Willy date some number k of the N, then marry the first one after number k that is better than all the previous women? Why shud this strategy be used? Why have this strategy been thought of?

Willy has two pieces of information about each person he dates:

1) How they rank compared to the other people he's dated previously - in particular, whether or not they're the best he's dated.
2) Where they are in the list of the N people he could ever date - in particular, how many people he's dated previously.

Since the goal is to marry the best of the N people, the strategy obviously has to be of the form:

A) Reject anyone who isn't the "best so far" - they can't be the best of the N.
B) Reject anyone at specified points in the order - the only other basis for deciding to reject someone.
C) Accept the first person you don't reject.

Fairly obviously, the chances of the best so far being the best overall increase as he goes on more dates, so if Willy's prepared to risk a false positive with the k'th person dated, then he should also be prepared to risk it with the (k+1)'th, so the optimal strategy looks like "reject the first k and pick the next person who's better than all of them"
 IP Logged
titan
Newbie

Posts: 33
 Re: Bachelor's Dilemma   « Reply #28 on: Oct 15th, 2013, 7:49am » Quote Modify

I think I'm getting it now. So here I go:-

He can date only some ladies. So, let it be k.
Now, he marries a girl based on the information he gathers by dating these k ladies.
Now, we don't know who he will marry out of the N-k. So, we add up all the possibilities. i.e. if he found k+1 is best or k+2 or k+3 and so on.
Now, when lets say he marries k+7 th girl, he secretly wants that best of all the k+6 girls shud have come up in the list he dated. So, we are multiplying these probabilities too with all the cases that either k+1 is best or k+2 or k+3 and so on!!
Am I right?

And since k can be anything from 1 to N-1, so, we have pretty much taken care of all cases.
And what if he dates just 1 lady and she is the best of N? We havn't taken into account for the case when he marries 1st date, I think, bcoz he only gets info by comparing! rightttt?
 « Last Edit: Oct 15th, 2013, 8:39am by titan » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: Bachelor's Dilemma   « Reply #29 on: Oct 16th, 2013, 5:19am » Quote Modify

on Oct 15th, 2013, 7:49am, titan wrote:
 And since k can be anything from 1 to N-1, so, we have pretty much taken care of all cases.   And what if he dates just 1 lady and she is the best of N? We havn't taken into account for the case when he marries 1st date, I think, bcoz he only gets info by comparing! rightttt?

When k=0 or k=N-1, then Willy only has a 1/N chance of marrying the best. When k=1 (assuming N>2), he has a better than 1/N chance - he has a 1/N chance that his first date is with the 2nd best, in which case he ends up with the best, but he also has a 1/N chance of it being with the 3rd best, in which case he then has a 1/2 chance of dating the best before the second best, so, just considering those two cases, he has a 1/N(1+1/2) chance of marrying the best - already better than the flat 1/N for settling for first or last...

So, yeah, he could settle for the first, but he only finds out about the distribution of women once he starts comparing them - after the first date, he has no idea whether it was good, bad, or about average, in comparison with the rest of the local dating pool...
 IP Logged
titan
Newbie

Posts: 33
 Re: Bachelor's Dilemma   « Reply #30 on: Oct 16th, 2013, 5:29am » Quote Modify

A small doubt I have.

Quote:
 Now, when lets say he marries k+7 th girl, he secretly wants that best of all the k+6 girls shud have come up in the list he dated.

He wud actually be wanting that best of all the N-1 wud have come in the list of girls he dated.
So, shudn't we be doing k/(N-1) n not k/(k+6).
Or is there any significance of numbering?
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »