wu :: forums
wu :: forums - Bachelor's Dilemma

Welcome, Guest. Please Login or Register.
Sep 25th, 2018, 5:35pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, william wu, Icarus, SMQ, ThudnBlunder, Grimbal, towr)
   Bachelor's Dilemma
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Bachelor's Dilemma  (Read 13612 times)
amstrad
Newbie
*





   


Gender: male
Posts: 10
Re: Bachelor's Dilemma  
« Reply #25 on: Mar 26th, 2007, 12:13pm »
Quote Quote Modify 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 Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Bachelor's Dilemma  
« Reply #27 on: Oct 15th, 2013, 7:16am »
Quote Quote Modify 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 Quote Modify 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? Cheesy
 
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? Cheesy
« Last Edit: Oct 15th, 2013, 8:39am by titan » IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Bachelor's Dilemma  
« Reply #29 on: Oct 16th, 2013, 5:19am »
Quote Quote Modify 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? Cheesy

 
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 Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board