Another week, another Riddler. This is a puzzle about maximizing a selection with limited resources:
From Julien Beasley, a new spin on the Sultan’s Dowry Problem, a classic problem of matrimony:
The sultan has asked her vizier to present her with 10 candidates for marriage. The vizier has searched the kingdom for the 10 most desirable partners, but he does not know whom the sultan will prefer. If she saw them all at the same time, she would easily be able to rank them from 1 (the best partner) to 10 (the worst partner). But the vizier can only present the candidates one at a time — very hard to sync everybody’s calendars, even back then — and in a random order. Upon seeing each candidate, the sultan must reject or accept him. If a candidate is rejected, the sultan cannot pick him again. But on seeing each new candidate, she knows exactly where he’d stack up relative to the candidates she has rejected. If she strategizes, what’s the highest rank she can expect her chosen candidate to have on average?
For example, if she simply accepted the first candidate presented to her, his rank could be anywhere from 1 to 10 with equal probability, averaging to 5.5. Surely she can do better…
This was a difficult problem. With each candidate you have more information to make a decision — but wait too long and you don’t get to make a decision.
Here are the acceptance criteria that I suggest using:
[N/A, N/A, N/A, 3, 4, 4, 5, 6, 7, 0]
What does this mean? Start by always letting the first three candidates pass. Then, if the next candidate is better then 3 of the previous candidates accept them. If you don’t, accept the next if they are better than 4 of the previous candidates. Continue like this through the array — always accepting the last candidate if you get there.
Using this method you will have a suitor with an average value of 8.34166
I hope to have an explanation of the math behind why this works later in the week