Originally posted by talzamir
An exact answer eludes me too. As I see it, the real decision to make is to decide how long one should skip taking a bride so I did some monte carlo on it. The right choice can be any number, but the second to last - the last girl to say "no" to despite her having the highest dowry to date.. is more manageable. The best strategy I've found is to keep saying ...[text shortened]... he survival rate is better than one in a hundred though.. about one in four or thereabouts.
I tried a dynamic programming approach to find the best strategy and must say I'm getting odds far below 25% of choosing correctly. My best strategy only claims 3,3% chance of making the right choice. My calculations are below.
Say strategy n is the strategy to wait until the nth woman and then choose the first who claims the largest dowry so far. Say p(n) are the odds that this strategy gives the right choice. Strategy 100 waits for the last woman. There is a 1% chance she has the largest dowry, so p(100) = 1%.
Now go to strategy 99. There is a 1/99 chance she claims the largest dowry so far. There is also a 1/2 chance that if she does, the 100th women still has a larger dowry. Then there is a 98/99 chance she doesn't have the largest dowry so far. In that case we'll wait for the 100th women, and waiting gives us the succes chance of strategy 100. In numbers this gives p(99) = 1/99*1/2+98/99*p(100).
In general we get the following formula. p(i) = 1/i*(1/(100-i+1)) + ((i-1)/i)*p(i+1).
Anyone sees anything wrong with this approach ? Might be a problem with the excel implementation as well.