Intereting Posts

Quadratic/ Cubic/ etc approximations without the Taylor series
Bases having countable subfamilies which are bases in second countable space
Uniform sampling of points on a simplex
Is there a size of rectangle that retains its ratio when it's folded in half?
Determinant of rank-one perturbations of (invertible) matrices
Proving Things About Rings Using Things About Vector Spaces
Is the Nested Radical Constant rational or irrational?
If $|a| = 12, |b| = 22$ and $\langle a \rangle\cap \langle b\rangle \ne e$, prove that $a^6 = b^{11}$
Ring of holomorphic functions
Combinatorics problem: $n$ people line up to $m$ clubs
Thoughts on the Collatz conjecture; integers added to powers of 2
An obvious pattern to $i\uparrow\uparrow n$ that is eluding us all?
Positive part of $y$ with $y\in L^2(0,T; H_0^1(\Omega))$ and $y'\in L^2(0,T; H^{-1}(\Omega))$
To find the limit of three terms mean iteration
How many elements in the finite field $F_{256}$ satisfy $x^{103}=x$?

Anyone have any ideas on this question? I think you have to use the pigeon hole principle..but I am not sure about that?

The numbers $1,2,3,\ldots,101$ are written down in a row in some order. Is it always possible to cross out $90$ numbers in a way such that all $11$ numbers left will stay either in increasing or decreasing order?

- Using Pigeonhole Principle to prove two numbers in a subset of $$ divide each other
- Smallest number of points on plane that guarantees existence of a small angle
- Pigeon hole principle with sum of 5 integers
- Distribution of points on a rectangle
- In a sequence of $n$ integers, must there be a contiguous subsequence that sums to a multiple of $n$?
- if there are 5 points on a sphere then 4 of them belong to a half-sphere.

- Combinatorics - pigeonhole principle question
- Number of horse races to determine the top three out of 25 horses
- How to check if a 8-puzzle is solvable?
- 100 blue-eyed islanders puzzle: 3 questions
- regarding Pigeonhole principle
- The Pigeon Hole Principle and the Finite Subgroup Test
- pigeonhole principle and division
- Ten soldiers puzzle
- Puzzle : There are two lengths of rope …
- Can the product $AB$ be computed using only $+, -,$ and reciprocal operators?

This is the Erdos-Szekeres theorem on monotonic subsequences. I’m pasting a proof from wikipedia:

Given a sequence of length $(r − 1)(s − 1) + 1$, label each number $n_ i$ in the sequence with the pair $(a_i,b_i)$, where $a_i$ is the length of the longest monotonically increasing subsequence ending with $n_i$ and $b_i$ is the length of the longest monotonically decreasing subsequence ending with $n_i$. Each two numbers in the sequence are labeled with a different pair: if $i < j $ and $n_i < n_j$ then $a_i < a_j$, and on the other hand if $n_i > n_j$ then $b_i < b_j$. But there are only $(r − 1)(s − 1)$ possible labels in which $a_i$ is at most $r − 1$ and $b_i$ is at most $s − 1$, so by the pigeonhole principle there must exist a value of $i$ for which $a_i$ or $b_i$ is outside this range. If $a_ i$ is out of range then $n_i$ is part of an increasing sequence of length at least $r$, and if $b_i$ is out of range then $n_i$ is part of a decreasing sequence of length at least $s$.

in your problem, take $r = s = 11$

suggested reading… some further exploration of monotonic subsequences: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i2r14

Associate with each element of the list an ordered pair $(a,b)$ where $a$ is the longest increasing subsequence ending on that number and $b$ is the longest decreasing subsequence starting with that number. Show that no two numbers can have the same pair associated because one can extend the subsequence of the other. There are only $100$ pairs with both entries $10$ or less.

- when we have circle in hyperbolic plane,what is the center and radius of this circle in Euclidean plane?
- Constructing a certain rational number (Rudin)
- Indefinite integral of secant cubed
- Localization at a prime ideal is a reduced ring
- Is the complement of the closed unit disk in the plane homeomorphic with $\mathbb R^2\setminus \{(0,0)\} $ ?
- Greibach normal form conversion
- What is the maximum point for which number of way to reach is given
- Morphism from a line bundle to a vector bundle
- Real Roots and Differentiation
- For what $n$ is $U_n$ cyclic?
- Showing that $ \displaystyle \lim_{n \rightarrow \infty} \left( 1 + \frac{r}{n} \right)^{n} = e^{r} $.
- $(-1)^{\sqrt{2}} = ? $
- Fermat's little theorem's proof for a negative integer
- weak derivative of a nondifferentiable function
- Multidimensional complex integral of a holomorphic function with no poles