Re: HSC 2016 MX2 Combinatorics Marathon
Cool question! Did you think of it yourself braintic?
Let's play this game with n doors.
I believe the optimal strategy is to refuse to switch until the final offer, and switch then. This guarantees you a (n-1)/n chance of success. (It fails if and only if your original choice was the correct door).
Sketch of proof of optimality:
We can consider the "value of a door" to be the expectation of the random variable that is 1 if this door is correct and 0 if it isn't. (Well, the conditional expectation, given the information that Monty successively gives us).
Each time Monty opens a door, he increases the value of all remaining unopened doors (excluding your current choice, because him opening a door gives you no information about your door!) And he also gives the now-open door a value of zero.
The way the value of these unopened doors increases is they scale by the same factor. (I.e they remain in the same proportion, they just "fill up" the value that that the removal of a door vacates).
This can be used to show that at every step, each unopened door has value >= 1/n, regardless of our choices. (Value of an unopened door never decreases).
This means on the last step, when we decide whether to reject a door or not, the minimum value we will be throwing away must be at least 1/n.
As we have shown we can indeed arrange this, (by never changing door beforehand), we are done.
Intuition behind this: Each time Monty opens a door he is telling us more about the unopened doors and making them more valuable. By never changing beforehand, there is the greatest differential in value between doors at the end.
. Want to justify this for everyone else's sake?
