Understanding solution to the secretary problem I am trying to understand the solution to the Secretary Problem (see, e.g., Wikipedia: https://en.wikipedia.org/wiki/Secretary_problem).
As I see it, it is usually solved in the following way:
(1) It is clear that the optimal solution is: Reject the first $r$ applicants (for some $r$), then take the next candidate which is better than all of them.
(2) Compute $r$.
I do understand (2), but how about (1)?  Why is the best solution of this form? On Wikipedia, I only found [reference needed]. So, could somebody explain the solution of the Secretary Problem to me?
 A: Partial answer but hopefully this may address one possible confusion (which, I'm guessing, is goal (A) vs goal (B) below).
You have to be very careful about the goal, or optimality criterion.  The goal of the problem is to (A) maximize the chance of selecting the very best candidate.  The goal is not to (B) select as good a candidate as possible.
Just to divert for a moment: if your goal is to (B) select as good a candidate as possible, and suppose for whatever reason you are down to the last 2 candidates, and the 2nd-last candidate X ranks higher than median, then you should take X, because on average the last (unseen) candidate will rank median.  However, if the goal is to (A) select the very best, then you should reject X even if X ranks 2nd-best so far, because if you select X you have failed, whereas if you reject X there is still a $1/n$ chance that the last unseen candidate is the very best.
Given goal (A), it is clear that at no stage should you accept a candidate who is not the very best seen so far.
So any best strategy must be of the form: at stage $t \in [1, n-1]$, do you accept/reject the current candidate if he/she is the best?
Technically, your strategy can make the accept/reject decision based on what you have seen so far, i.e. the order of the appearance of the previous candidates.  E.g. your strategy could in stage 7 make different decisions depending on whether the 1st-appearing candidate is better or worse than the 4th-appearing one.  However, given the random initial ordering of the pool, it makes no sense for the best strategy to use that information.  I can't really call this a "proof" :) but I hope it's "obvious".
So any best strategy must be of the form: at stage $t \in [1,n-1]$, do you accept/reject the current candidate if he/she is the best, as a function of only $t$?  In other words, the best strategy can be described as an $(n-1)$-bit vector, where the $t$-th bit describes whether to accept if the $t$-th round current candidate is the best seen so far.  
It remains to show some form of monotonicity, i.e. there exists some $r$ s.t. the best strategy is to reject if $t \le r$ and accept if $t > r$, and that such a vector (of the form $[0,0,...,0,1,1,...1]$) beats any other vector (w.r.t. the goal of maximizing chance of selecting the very best).  This part I cannot prove easily.  I imagine the proof is that if you have a vector like $[0, 0, 1, 0, 1,...,1]$ you will need to show that it is worse than either $[0,0,1,...1]$ or $[0,0,0,0,1...1]$.  Some of the dynamic programming references might help...?
