4.1: El Principio del Agujero de Paloma

Se dice que una función$f:X \rightarrow Y$ es 1—1 (leer uno a uno) cuando$f(x) \neq f(x′)$ para todos$x,x′ \in X$ con$x \neq x′$. Una función 1—1 también se llama inyección o decimos que$f$ es inyectable. Cuando$f:X \rightarrow Y$ es 1—1, lo notamos$|X| \leq |Y|$. Por el contrario, tenemos la siguiente afirmación evidente, que popularmente se llama el principio de “Agujero de Paloma”.

Proposición 4.1. Principio de Agujero de Paloma

Si$f: X \rightarrow Y$ es una función y$|X|>|Y|$, entonces existe un elemento$y \in Y$ y elementos distintos$x,x′ \in X$ para que eso$f(x) = f(x') = y$.

En un lenguaje más casual, si debes meter$n+1$ palomas en$n$ agujeros, entonces debes poner dos palomas en el mismo hoyo.

Aquí hay un resultado clásico, cuya prueba se desprende inmediatamente del Principio de Agujero Paloma.

Teorema 4.2. Teorema de Erdós/Szekeres

Si$m$ y$n$ son números enteros no negativos, entonces cualquier secuencia de números reales$mn+1$ distintos tiene una subsecuencia creciente de$m+1$ términos, o tiene una subsecuencia decreciente de$n+1$ términos.

Prueba

Dejar$\sigma = (x_1,x_2,x_3,...,x_{mn+1})$ ser una secuencia de números reales$mn+1$ distintos. Para cada uno$i=1,2,…,mn+1$, deja$a_i$ ser el número máximo de términos en una subsecuencia creciente de$\sigma$ con$x_i$ el primer término. También, deja$b_i$ ser el número máximo de términos en una subsecuencia decreciente de$\sigma$ con$x_i$ el último término. Si hay algunos$i$ para los cuales$a_i \geq m+1$, entonces$\sigma$ tiene una subsecuencia creciente de$m+1$ términos. Por el contrario, si para algunos$i$, tenemos$b_i \geq n+1$, entonces concluimos que$\sigma$ tiene una subsecuencia decreciente de$n+1$ términos.

Queda por considerar el caso donde$a_i \leq m$ y$b_i \leq n$ para todos$i=1,2,…,mn+1$. Ya que hay pares$mn$ ordenados de la forma$(a,b)$ donde$1 \leq a \leq m$ y$1 \leq b \leq n$, concluimos del principio de Paloma Agujero que debe haber enteros$i_1$ y$i_2$ con$1 \leq i_1 < i_2 \leq mn+1$ para los cuales$(a_{i1},b_{i1})=(a_{i2},b_{i2})$. Desde$x_{i1}$ y$x_{i2}$ son distintos, o bien tenemos$x_{i1}< x_{i2}$ o$x_{i1}>x_{i2}$. En el primer caso, cualquier subsecuencia creciente con$x_{i2}$ como su primer término se puede extender$x_{i1}$ anteponiendo al inicio. Esto demuestra que$a_{i1}>a_{i2}$. En el segundo caso, cualquier secuencia decreciente de con$x_{i1}$ como último elemento se puede extender sumando$x_{i2}$ al final. Esto muestra$b_{i2} > b_{i1}$.

En el Capítulo 11, exploraremos algunas generalizaciones poderosas del Principio de Agujero de Paloma. Todos estos resultados tienen el sabor de la aseveración general de que el desorden total es imposible.