4.1: El Principio del Agujero de Paloma

Última actualización
Guardar como PDF

Page ID: 118472

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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.