Re: HSC 2016 MX2 Combinatorics Marathon
Here is a fun one to think about. Please refrain from answering if you have seen this question before in some guise.
Shadowdude has n first dates with n of his crushes over the course of a day. He would like to ask one of them out to a second date, and he would very much like to choose the "best" one. Nothing less will suffice. Unfortunately these women all know each other, so he can only choose one, and if he doesn't organise a second date with a woman at the end of his first date with her, he loses all future opportunities with her.
What strategies can you come up with for Shadowdude to maximise his probability of choosing the best possible girl to ask out to a second date? What probability does this ensure?
What happens to the strategy and the probability of success as n gets large? I.e. If n is massive, is there much hope of making the best choice?
Assumptions:
-Upon having a first date with a girl, Shadowdude can immediately assign her a real number out of 10 that quantifies how ideal she is for him.
-These real numbers are distinct, and so provide a strict ordering.
As we have had no takers yet, I will break this down.
A
strategy in this problem is a method for decisionmaking that can tell you whether or not to accept the k-th candidate, given only the information of how this candidate stands in relation to the (k-1) prior. Any such strategy gives you an overall probability of success, where success is defined to be the event of you choosing the best candidate of all. The aim of this question is to find a strategy (dependent on n of course) that is optimal (at least as good as any other strategy), and explicitly compute the success probability for this strategy.
a) We say the k-th candidate is "best yet" if they are better than the (k-1) prior. Explain why we can assume that S(n) rejects any candidates that are not best yet.
b) The work of a) means we can identify the strategies S(n) we care about with subsets A(n) of the positive integers {1,...,n}. Following the S(n) strategy then involves selecting the k-th candidate iff they are both "best yet" and k is an element of A(n). (Note that if a candidate is best yet, that is all the relevant information yielded by the interviews of the earlier candidates, the ordering of prior candidates is irrelevant.) Show that thanks to optimality we can assume that A(n)={m+1,...,n} for some m < n dependent on n. Interpret this fact in terms of an information gathering process. Intuitively, how should we expect the optimal m for a given n to vary as n gets large?
c) The work of b) means we have cut down the strategies we care about even more. Now a strategy amounts to rejecting the first m candidates and thereafter selecting the first candidate that is "best yet". Why is this a bad strategy for m very close to 1 or very close to n? Find an expression for the success probability in terms of m and n.
d) We are now interested in the limiting behaviour as n gets large. By looking at the structure of the success probability computed in c), suggest an optimal* choice for m in terms of the large integer n, and compute the limit of the success probabilities as n->inf.
(*) Actually showing that our choice of m is optimal for a given n is not simple/nice as far as I know, but there is certainly a logical choice for m that will be near-optimal and behaves optimally in the limit. Depending on how much analysis you want to do you can make stronger claims here. (Eg, for sufficiently large but fixed n, is S(n) optimal? How large must n be for this to be true?)
