A question about proof of Bolzano-weierstrass theorem. The proof of Bolzano-Weierstrass theorem in my textbook goes something like this. First, they construct a sequence of nested intervals such that $A_n$ (the sequence of left endpoints) and $B_n$ (sequence of right endpoints) tend to the same limit. Then, they claim that if one chooses $A_{n_1} \in [A_1,B_1]$, $A_{n_2} \in [A_2,B_2]$ such that $n_2 > n_1$ and so on, that the subsequence $A_{n_k}$ will be convergent.
My question is, if at each step we choose such $n_k$ that $A_{n_k}$ is as small as  possible, is the resulting subsequence guaranteed to be monotonic as well?  
 A: I'm not sure the proof you've given works, but the statement is true: every sequence has a monotonic subsequence. In fact, this then implies Bolzano-Weierstrass since bounded monotonic sequence must converge.
A fun proof of this uses graph theory and something called the infinite Ramsey theorem. This says if you colour the edges of a complete infinite graph in finitely many colours, there is guaranteed to be a monochromatic infinite complete subgraph.
To apply this, for a sequence $(x_n)$ construct a infinite complete graph on the positive integers. Then colour an edge $ij$ blue if $x_i \leq x_j$ ($i < j$) or red otherwise. By infinite Ramsey you have a complete infinite subgraph, which corresponds exactly to a monotonic subsequence.
A good exercise in analysis is to prove that every sequence has a monotonic sequence without using graph theory. One of the reason's I doubt you can just prove this by picking $A_{n_k}$ as small as possible is that the subsequence may be monotonic increasing or decreasing.
