In the last column, I introduced an extension of the Sultan’s daughters puzzle that was posted by Brian.
In the original version, a young man is presented with the Sultan’s 100 daughters one at a time. He can choose to marry whichever one has just been introduced, but cannot go back to any of the previous ones. The catch is that he must pick the one with the biggest dowry. If he chooses any other daughter, instead of losing his head in love, he will simply lose his head. The best strategy for choosing increases his chances from 1% to 37%. This surprising result requires some computation to derive.
So much for the standard version: The extension assumes that instead of one young man, the sultan has a flock of eager young men who all face the same challenge. They are called in one at a time and allowed to choose. If a young man guesses the right daughter, the game stops, if he makes a mistake, the next young man is called in and the game starts over with the same ordering of daughters. This continues until either we have a winner or the sultan runs out of young men willing to risk everything. However, all these young men are good at mathematics and after the first dozen or so fail to come back, the next ones in line start talking amongst themselves and decide that the standard strategy has resulted in the deaths of their colleagues. They assume all predecessors let 37 daughters pass and picked the next one with a higher dowry unless there were none with a higher dowry because the winner was in the first 37. Therefore a different strategy must be developed knowing that additional bit of information. What is it? They all realize what the modification must be and eagerly watch as the first smart one is called. What happens?
My approach to solving this variation was to adopt the position of the next suitor called. He doesn’t have much time, and his laptop has not yet been invented, so he must come up with something in his head that is probably correct, but he can afford to leave a detailed proof until later (assuming he has a later). With that in mind, cheating is fair.
I simply assumed the original method scales. The next suitor knows the distribution has two parts: the first has 37 daughters and the second has 63. Treat the first part like a scaled-down new problem. Instead of 100 daughters, only consider 37. Then 37% of 37 gives 14. So the suitor skips the first 14 and takes the daughter who comes next and has a higher dowry than any of the first 14. But if none of the daughters from 15 to 37 have a higher dowry, then he must apply the same strategy to the second part of the distribution. Only here he realizes that he will fall into the same trap of the first suitor who lost his head because the next daughter with a higher dowry is a known loser. Therefore his best strategy is to take the second daughter who has the highest dowry so far.
After coming up with my solution by plausible reasoning (that is, unproven, but likely, and therefore useful when being escorted into the throne room), I cheated again, looked at the answer, and found that Brian’s solution was the same! The system can be extended. After all, the strategy does not promise a win – it only maximizes the chances of winning. If the smart suitor loses, and if the second smart suitor knows a new strategy that his predecessor used, then he can further extend it.
This leads to two more questions: what is the probability of winning at each iteration? We know that the first iteration of smart reasoning raised the probability from 1% to 37%. Intuitively we feel that the modified version must have a higher probability of success simply because it was based on more knowledge of the system (i.e. the first guy died). How does the probability of success change with each iteration? Does a time come when a suitor is guaranteed of success?
While you are pondering that, I have not forgotten about my earlier poser to the readers about the safety of travel. I asked readers to derive and submit to me their analysis of where the cross-over point is on deciding which is safer, driving or flying. In the spirit of plausible reasoning, we believe that such a cross-over point exists because at very short distances, an airplane must take off and land, both of which are relatively risky compared to cruising at altitude, and therefore driving is safer for very short distances, but over large distances, the relatively safe cruising of the airplane dominates, while a driver will be exposed to a variety of traffic including rush hours, drunk drivers, drive-by shooters, sleepiness, etc.
Obviously many other factors also come into play including just what parameters are truly relevant. Is exposure time more important than accidents per mile? Spacecraft have by far the fewest accidents per passenger mile of any vehicle. Does that make them the safest?
I am still hearing from people about this issue and will devote a couple of columns to it in the near future. If you have any input, let me know.
In response to the interest my original tutorial generated, I have completely rewritten and expanded it. Check out the tutorial availability through Lockergnome. The new version is over 100 pages long with chapters that alternate between discussion of the theoretical aspects and puzzles just for the fun of it. Puzzle lovers will be glad to know that I included an answers section that includes discussions as to why the answer is correct and how it was obtained. Most of the material has appeared in these columns, but some is new. Most of the discussions are expanded compared to what they were in the original column format.
[tags]decision theory,sultan daughter puzzle,extend strategy,travel danger,iteration[/tags]