Brain Teaser No 1

So a strategy that throws a number of daughters away in order to gain some information about the likely dowry levels increases your chances of picking the highest.

The simulation I did presents 10 daughters, each with a different dowry, in every possible order and counts the times that a given strategy ends up in marriage. You can improve your chances from 10% to nearly 40%.

Paul

Paul

Paul

quote:

---

Say you decide to pick the 4th daughter, the first 3 go by with dowries of 2, 4, and 3, daughter 4 is presented with a dowry of 1. You'd be dumb to pick her because you know she doesn't have the highest.

---

You are not, as I understand it, told what dowry the daughter you do not pick has. The only information is that, when you choose you have chosen correctly or not - and then the game is over.

You must decide which to pick as she appears. You have no way of knowing who has the largest dowry and not picking someone does not give you any more information on that. It might be #1 or #2 or...#10 with equal probability.

But since you cannot know who has the highest dowry, and the chance of it being daughter 1 is no less, or more, likely than any other.

Oner

quote:

---

More "complex" ways, like picking the first bride that is larger than maximum(#1,#2) are needed to overcome the 0.1 barrier.

---

But you have no way of knowing that.

cheers

Nigel

quote:

---

Knowing what ? I know the dowries of #1 and #2, I now choose the first bride between 3...10 that has a larger dowry than both 1 and 2.

---

But if daughter 1 has the highest dowry, and the chance of that is equal to any other daughter, then your strategy, such as it is, would fall down straight away. Your strategy seems to based on #1 not being highest, or #2 not being highest - but of course #1 or #2 are equally probable to be highest are they not?

cheers

Nigel

quote:

---

You are not, as I understand it, told what dowry the daughter you do not pick has. The only information is that, when you choose you have chosen correctly or not - and then the game is over.

---

Here is the original problem,

quote:

---

You will be presented with the daughters one at a time and, as each daughter is presented, you will be told the daughter's dowry (which is fixed in advance). Upon being presented with a daughter, you must immediately decide whether to accept or reject her (you are not allowed to return to a previously rejected daughter).

---

You can see it is clear that the daughter appears, you get told the dowry, and you choose. So for any particular daughter you know the dowries of each previous plus the one you must decide on.

quote:

---

But if daughter 1 has the highest dowry, and the chance of that is equal to any other daughter, then your strategy, such as it is, would fall down straight away. Your strategy seems to based on #1 not being highest, or #2 not being highest - but of course #1 or #2 are equally probable to be highest are they not?

---

The strategy increases your chances of a correct guess.

The simulation I knocked up tries every possible permutation of the 10 daughters against the strategies and counts how often they win.

The interesting bit is to analytically confirm its conclusions.

There's nothing particularly clever about the code for the simulation, it's just a hack I can provide to anybody who wants it.

Paul

quote:

---

You can see it is clear that the daughter appears, you get told the dowry, and you choose. So for any particular daughter you know the dowries of each previous plus the one you must decide on.

---

But if #1 has the highest and you do not pick her you are out anyway. Everything people have put forward so far seems to based on the premise that #1 is not, nor ever will be , the highest? Is your strategy never to pick #1?

cheers

Nigel

quote:

---

Everything people have put forward so far seems to based on the premise that #1 is not, nor ever will be , the highest?

---

If you pick #1 you have a 0.1 probability of being right. And obviously a 0.9 probability of being wrong. Using the 'strategy' you have a 0.4 probability of winning. Which is better than 0.1....

quote:

---

Is your strategy never to pick #1?

---

The strategy requires never picking #1.

Paul

PROBABILITY. Assuming the daughters are presented in random order, the probability that Daughter #1 has the biggest dowry is 0.1. Ditto for daughters #2 thru 10.

STRATEGY. Whatever (passive) strategy you adopt will NOT change the above probabilities.

HOWEVER

If your strategy is to predetermine (before the parade) that you will chose #4 (say) irrespective of any other information available at the time of choice, then the chances of winning are still only 0.1. This is clearly not a very good strategy! Same applies whether you predetermine #1, 2, 3, 5, 6…..etc

A better strategy would be to predetermine (say) #4, but only actually chose #4 providing she has the highest dowry so far. If not, then chose the first subsequent daughter to be presented with the highest dowry so far. Startegy can apply to predetermining any #1 thru 10.

Of course, if you predetermine to chose #1, this second strategy doesn't provide you with any more information than the first strategy. Likewise if you predetermine #10. So your chances will remain at 0.1 for both #1 and #10, but increase for the others.

Paul R's proposal can be rephrased to ALWAYS predetermine #5 providing her dowry is the largest so far. If not, then chose the first daughter from #6; #7; #8; #9; #10 that is larger than #1>4. Of course, there is a 40% chance that the largest dowry IS held by #1, 2, 3 or 4 (and you loose!) There is also the chance that the first dowry from #5, 6,....10 that is bigger than 1 to 4, is not the biggest dowry from 5 to 10 (and you loose!)

I am surprised that the last strategy (Paul R's)improves the chances of winning to as much as 0.4, but this is no more than a gut feeling.

I realised I used the word ALWAYS. This implies we play the game many times. This is the easiest way to look at some probabilities. If the game is played often enough using the same strategy, then the number of successful outcomes should closely match the mathematical probability. Hard though it may seem, the best strategy for winning lots of games is usually the best strategy to adopt even when you only get one go at the game!

Apologies Nigel, I've just re-read this and it’s a bit long-winded - chances are (=big pun) you rightly gave up after the first few lines

Cheers

Don

This is NOT stated in Bam's puzzle.

ASSUME, for the moment, that Paul R's strategy and calculation are the best Assuming the daughters are presented in random order. Lets adopt this strategy but find ourselves at daughter number 5 with the dowrys having INCREASED steadily, from 1 thru 5. The chances of this happening RANDOMLY are pretty small!

Perhaps, we have now REALISED that the King is indeed a friend. He couldn't have put the girls on parade in decending order, because any young chap with a bit of sense would HAVE to adopt a strategy that lets the first few girls go by, therby loosing.

So, I suggest we adopt Paul R's strategy, with the condition that IF the first 5 dowrys are in assending order, this is a clear signal from the King that they are ALL in assending order, and we wait for #10

All those in favour, say "aye"

Cheers

Don

quote:

---

I am surprised that the last strategy (Paul R's)improves the chances of winning to as much as 0.4, but this is no more than a gut feeling.

---

It would be nice to see some maths confirming the exhaustive search.

It's obviously possible that there's a bug in my code.....

Oh. Aye!

Paul

Just for fun I tried this out. Using two random number generators (my children) the results were:

#1 - 77; #2 - 223;#3 - 267#4 - 273; #5 - 159 #6 - 63; #7 - 181; #8 - 71; #9 - 127; #10 - 151.

cheers

Nigel

Yes it would you bunch of wimps. Come on you lot - cut out this weedy simulation stuff and let's see some hard graft calculations. Get those pencils sharpened!

BAM
(How to win friends and influence people)

cheers

Nigel

No, only 2 to my knowledge.

As my grandmother used to say...

"Maternity is a matter of fact. Paternity will always be a matter of opinion!"

Cheers

Don

BAM
(How to win friends and influence people)

Concentration on the ladder problem is slipping again....OTOH, I am visualising a further use for that rickety old ladder, the tea chest and that length of rope with a noose in it that is currently tied round that poor goat's neck.......

BUT, we don't want any accidents to befall dear old Bam BEFORE we sort the ladder problem....

Cheers

Don

'If I assume a random chance that each of these daughters has been allocated the largest dowry and that I know the dowry of each daughter when they are presented'

I can look at like this.

I pick the first daughter, probability that she is the one is 1/10, probability that she is not is 9/10, obviously I choose not.
Second daughter, we do not choose her if the dowry is lower then daugher 1 but we could choose her if the dowry is above 1, therefore the information gained by letting daughter one past is beneficial and improves on the 1/10 chance.

Paul's approach works.

Equation time

This will not comprehensive as I don't care that much.
Assume I allow daughter 1 to go and then pick the next daughter with a higher dowry
1/10 D1 (daughter one) is the one, fail 1/10*0
1/10 D1 is second highest so chance of picking the one is 1/10*1
1/10 D1 is third highest probability that next higher dowry is highest is 1/10*1/2
1/10 D1 is fourth highest probability that next higher is highest is 1/10*1/3
etc
therefore probablility of success is
1/10*(0+1+1/2....1/9)=0.282897

P (Probability) that either is first is 2/10
P that D1 is second and D2 not first 1/10*8/9
P that D2 is second and D1 not first 8/10*1/9
P that D1 or D2 second but not first is 2*8/90 (in his case you will successfully pick highest dowry)
P that D1 is third and D2 not first or second 1/10*7/9...
P of D1 or D2 being third max is 2*7/90 and P that of remianing 7 the fist above D1 or D2 is highest is 1/2
therefore
2/90*(1*8+1/2*7+1/3*6+1/4*5+1/5*4+1/6*3+1/7*2+1/8*1)=0.365794

You may continue for more combinations and find some rule but I will stop here!

Matthew

Matthew

Nice work. Paul R's table is based on simulations, which is really a nice way of saying they are empirical, ie not dead accurate. but never mind, 'cos games of chance aren't predictable either!!

Anyway, Paul's table puts #3 and #4 daughters sooooooo close together, we can't really be sure that #3 has the slight edge.

Any chance you could do the number crunching (you do seem to do it rather well!!) for daughters 3 and 4, just to be certain. I wouldn't like to hesitate on #3, if it is #4 we should be waiting for.

Who knows, one day this knowledge might just be useful.....now who knows a King with 10 daughters.......

Cheers

Don

quote:

---

Nice work. Paul R's table is based on simulations, which is really a nice way of saying they are empirical, ie not dead accurate. but never mind, 'cos games of chance aren't predictable either!!

---

My simulation is empirical, but it is also exact since it examined every possible way of presenting 10 princesses.

It runs in about 45seconds and took less time to write than I've spent composing after the event posts....

Paul

I created a couple of simple simulations in excel for earlier problems. They didn't give "exact" answers because my computer doesn't generate exact sets of random numbers....just like real life doesn't. eg throw a real (but fair) dice (say) 36 times and the chances are that you won't get 6xOnes; 6xTwos; 6xThrees.....etc. Generate 36 random numbers in a computer and its unlikely you will get 6xOnes; 6xTwos; 6xThrees.....etc either. But the simulations did cover all the possible outcomes in each game. The bigger the number of times I ran each simulation, the closer was the simulated game result to the mathematically "exact" probability. eg the chances of throwing a One (say) improved towards 0.1666

My comment in the above post was made on the unjustified presumption that your simulation was similar to mine.....sincere apologies. The underlying work and the logic used in your simulation are clearly good.... and the " gut-feeling" refered to in my even earlier post, was like many gut feelings, probably wrong!!!!

Cheers

Don

With the princesses generating every permutation is very easy, and there are only 3,628,800 of them....

Paul

Don

You have used your computer to identify, and catalogue, the full possibility space, ie ALL the possible permutations of daughters and dowrys and sequences in which they could be presented. You have then used your computer to count the number of successful outcomes for a range of strategies, each based on your statement of "let X daughters go by, then pick the first with a higher dowry". I appreciate your program probably works more efficiently than as outlined above.

As you pointed out, the probability curve is skewed towards to lower numbers. Moral? don't let too many nice girls go by before choosing!

You also ask "is there a better strategy?"…….. the jury's still out.

Could we predict the outcome of a better strategy without knowing that strategy? probably, but then it would be blooming frustrating knowing there was a better answer and not knowing how to get to it.........now this leads me to a feeling of déjà vu…..

Cheers

Don

In the attached diagram, the three circles A, B and C have radii of 1, 2 and 3 respectively. What are the radii of the two 'fourth' circles, that can be made to just touch each of A, B and C. (note the two 'fourth' circles will not touch each other, cos that would break the golden rule!!)

Oh! BTW, there is a standard way and an elegant way to solve this little problem. The normal way will do for most, but in the case of Bam………..

Cheers

Don