Principio extremo#

Introducción#

El principio extremo es una técnica que ayuda a resolver problemas matemáticos. Se basa en el principio del buen orden de los números naturales, que dice que cualquier subconjunto no vacío de naturales debe tener un elemento mínimo. Esto se puede aprovechar de varias maneras en la resolución de problemas matemáticos pues puede ayudar a demostrar la existencia o imposibilidad de existencia de objetos con ciertas propiedades.

Principio extremo constructivo#

El principio extremo puede servir para mostrar que debe existir un objeto que cumple cierta propiedad. Un uso típico de esto tiene los siguientes pasos.

  1. Tomamos una propiedad \(P\) que queremos que tenga un objeto \(x\) de cierto conjunto no vacío \(X\).

  2. Tomamos una función \(f:X\to \mathbb{N}\) especial que viene del contexto dado.

  3. Demostramos que si \(x\) es un objeto que no cumple \(P\), entonces se puede construir a partir de él un objeto \(y\in X\) tal que \(f(y)\lt f(x)\).

  4. Por el principio del buen orden, debe exisitir un elemento \(x_0\) que minimice a \(f\). Como minimiza \(f\), por el inciso anterior debe de cumplir \(P\).

Veamos un ejemplo de la aplicación de esta técnica.

Problema. Se tiene un grupo finito de personas. Se sabe que cada quien tiene como mucho tres enemigos de entre las personas en el grupo. Muestra que es posible poner a las personas del grupo en dos cuartos de modo que en cada cuarto cada persona tenga a lo mucho un enemigo dentro de ese cuarto.

Solución. Para cada acomodo de personas en dos cuartos, una enemistad activa es una pareja de personas que son enemigas y están en el mismo cuarto. La enemistad total del acomodo es la cantidad de enemistades activas.

Si se tiene un acomodo que no cumple lo que queremos, es porque quedó una persona \(P\) con por lo menos dos enemigos en su cuarto, creando por lo menos dos enemistades. Pero entonces en el otro cuarto \(P\) tiene como mucho un enemigo. Así, si cambiamos a \(P\) de cuarto entonces la enemistad total del acomodo decrece pues se cambian al menos dos enemistades activas por a lo mucho una enemistad activa.

Consideremos al acomodo de personas con la menor enemistad total. Por el principio extremo constructivo, en este acomodo cada quien tiene como mucho un enemigo en su cuarto.

\(\square\)

Aunque el principio extremo esté explicado arriba mediante el uso de números naturales, en realidad el argumento funciona de la misma manera cuando la función que construimos cae a un conjunto que sabemos que está acotado, por ejemplo un conjunto finito. El siguiente problema geométrico es un ejemplo de esto.

Problema. Se tienen \(n\) puntos rojos y \(n\) puntos azules en el plano, todos ellos distintos y en posición general (no hay tres alineados). Muestra que es posible unir con un segmento de recta a cada punto rojo con uno y sólo un punto azul, de manera que no haya dos de estos segmentos que se intersecten.

Solución. Tomemos un acomodo de segmentos que unan a cada punto rojo con uno y exactamente un punto azul. Su longitud total será la suma de las longitudes de todos los segmentos dibujados.

Supongamos que tenemos un acomodo de segmentos en donde hay dos segmentos que se intersectan. Entonces, si nos fijamos sólo en estos dos segmentos, entonces tendríamos algo como en la parte izquierda de la siguiente figura.

Argumento principio extremo

Cambiemos los segmentos \(AC\) y \(BC\) por los segmentos \(AB\) y \(CD\), como en la parte central de la figura. Afirmamos que en este acomodo la longitud total es menor. En efecto, haciendo referencia a la parte derecha de la figura y usando desigualdad del triángulo tenemos que:

\[\begin{align*} AB+CD&= x + y\\ &< (a+b) + (c+d)\\ &= (a+c) + (b+d)\\ &= AC + BD. \end{align*}\]

La desigualdad es estricta pues no hay puntos alineados.

Consideremos entonces la forma de trazar segmentos con menor longitud total. Por el principio extremo constructivo, en ella no hay dos segmentos que se intersecten.

\(\square\)

Principio extremo destructivo#

El principio extremo también puede servir para mostrar que cierto objeto con cierta propiedad no puede existir. Cuando queremos hacer esto, usualmente seguimos los pasos descritos a continuación.

  1. Tomamos una propiedad \(P\) que queremos ver que no tiene ningún objeto \(x\) de cierto conjunto \(X\).

  2. Tomamos una función \(f:X\to \mathbb{N}\) especial que viene del contexto dado.

  3. Demostramos que si \(x\) es un objeto que cumple \(P\), entonces se puede construir otro objeto \(y\) que cumple \(P\) tal que \(f(y)\lt f(x)\). Así, podríamos producir elementos \(y_1,y_2\ldots\) con \(f(y_1)\gt f(y_2) \gt f(y_3) \gt \ldots,\) pero esto es imposible pues no puede haber una sucesión infinita decreciente de elementos en \(\mathbb{N}\).

  4. Así, no debe haber elementos de \(X\) que cumplan \(P\).

Veamos cómo resolver un problema clásico usando esta idea.

Problema. Demuestra que \(\sqrt{2}\) es un número irracional.

Solución. El conjunto que tomaremos es \(\mathbb{Q}\), el de los números racionales. La propiedad que no queremos es que un elemento de \(\mathbb{Q}\) sea igual a \(\sqrt{2}\). Consideremos \(f:\mathbb{Q}\to \mathbb{N}\) dada por \(f(\frac{p}{q})=p+q.\)

Supongamos que existe una fracción \(\frac{p}{q}\) que sea igual a \(\sqrt{2}\). Podemos suponer que \(p>0\), pues es distinto de cero y si fuera negativo podemos cambiar el signo en el numerador y denominador.

Tendríamos entonces que \(\frac{p}{q}=\sqrt{2}\), por lo que al elevar al cuadrado y multiplicar por \(q^2\) sucedería que \(p^2=2q^2\). Como \(2q^2\) es número par, entonces \(p\) también debe ser par, para que su cuadrado sea par. Así, podemos escribir \(p=2a\) (notemos que entonces \(a\lt p\)). De este modo, tenemos

\[2q^2=p^2=(2a)^2=4a^2.\]

Dividiendo entre \(2a^2\) y sacando raíz, obtenemos que \(\frac{q}{a}=\sqrt{2}\). Así, obtenemos otra fracción que cumple ser igual a \(\sqrt{2}\).

¿Cómo cambia el valor de \(f\)? Notemos que

\[f\left(\frac{q}{a}\right)=q+a<p+q=f\left(\frac{p}{a}\right),\]

así que \(f\) disminuye. Por el principio extremo destructivo, no debe existir entonces ninguna fracción igual a \(\sqrt{2}\) pues eso causaría una sucesión estrictamente decreciente e infinita de números naturales.

\(\square\)

En algunas situaciones se tienen que aplicar ligeras variantes del proceso descrito anteriormente, que no necesariamente hacen referencia directa a los números naturales. Veamos un ejemplo geométrico.

Problema. Muestra que no existe ningún conjunto finito \(X\) de puntos en la recta real tal que cada punto de \(X\) sea el punto medio de otros dos puntos en \(X\).

Solución. Supongamos que existiera uno de estos conjuntos. Tomemos cualquier punto \(x\in X\). Para que sea el punto medio de otros dos, entonces debe tener un punto \(p\) de \(X\) a la izquierda y otro a la derecha. Pero entonces para cada punto de \(X\) debe suceder que debe haber otro punto de \(X\) a la izquierda. Esto es imposible, pues como \(X\) tiene una cantidad finita de puntos, debe tener uno que esté lo más a la izquierda posible. Ese no tiene puntos a la izquierda y por lo tanto no puede ser punto medio de dos puntos de \(X\).

\(\square\)

Tarea moral#

Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.

  1. Se tienen puntos \(P_1,P_2,\ldots,P_n\) en el plano. No hay tres de ellos colineales. Muestra que es posible crear un polígono que use a estos vértices como puntos, y tal que no tenga lados que se intersecten en su interior (i.e. que no sea un polígono cruzado).

  2. Muestra que no existen soluciones en enteros positivos \(a,b,c,d\) a la ecuación

    \[7(a^2+b^2)=c^2+d^2.\]

  3. Se tiene una cantidad finita de puntos en el plano. Cada uno está coloreado de un color, ya sea rojo, verde o azul. No hay tres de ellos colineales. Muestra que hay un triángulo con un vértice rojo, uno verde y uno azul, de manera que dentro de él no hay ningún otro punto del conjunto.

  4. Sean \(a,b,c,d\) números enteros positivos tales que \(ab=cd\). Demuestra que existen números enteros positivos \(p,q,r,s\) tales que \(a=pq\), \(b=rs\), \(c=pr\) y \(d=qs\).

  5. Se tienen puntos \(P_1,P_2,\ldots,P_n\) en el plano. Se sabe que cada que se toma dos de estos puntos, hay otro de estos puntos en la recta que los une. Muestra que todos los puntos están alineados. Como sugerencia, supón que esto no es cierto. Para cada punto \(P\) y cada línea \(\ell\) formada por otros dos puntos, considera la distancia de \(P\) a \(\ell\). Usa la hipótesis para conseguir una sucesión infinita de estas distancias que sea decreciente.