Identificarse Registrarse

Psu
Enseñanza Básica
Enseñanza Media
Universidad
Olimpiadas
Comunidad



 
 Reply to this topicStart new topic
> Principio Extremal
Luffy
mensaje Jan 19 2015, 08:14 AM
Publicado: #1


Dios Matemático Supremo
Ícono de Grupo

Grupo: Usuario FMAT
Mensajes: 556
Registrado: 16-August 06
Desde: Rio de Janeiro
Miembro Nº: 1.950
Nacionalidad:
Colegio/Liceo: Instituto Nacional
Universidad: Instituto Nacional de Matematica Pura e Aplicada (IMPA)
Sexo:



Ya muchachos para que sigan entrenando les dejo un comentario sobre una tecnica muy simple pero a la vez muy poderosa. En muchos lados le llaman el Princicpio Extremal:
Consideren TEX: $A$ un conjunto cualquiera, y TEX: $\mathcal{R}$ una relación de orden en TEX: $A$, es decir, TEX: $\mathcal{R}$ es un conjunto de pares ordenados de elementos de TEX: $A$ (osea TEX: $R\subset A\times A$) tales que:
(i) TEX: $\mathcal{R}$ es reflexiva: TEX: $\forall a\in A: (a,a)\in \mathcal{R}$,
(ii) TEX: $\mathcal{R}$ es antisimétrica: TEX: $\forall a,a'\in A: (a,a')\in \mathcal{R}\wedge (a',a)\in\mathcal{R}\Rightarrow a=a'$,
(iii) TEX: $\mathcal{R}$ es transitiva: TEX: $\forall a,a',a''\in A: (a,a')\in \mathcal{R} \wedge (a',a'')\in \mathcal{R} \Rightarrow (a,a'')\in \mathcal{R}$.
Cuando TEX: $(a,a')\in\mathcal{R}$ se suele denotar TEX: $a\mathcal{R} a'$. Se dice que el par TEX: $(A,\mathcal{R})$ es un conjunto ordenado. Veamos algunos ejemplos:

1) Los números reales TEX: $\mathbb{R}$ pueden ser ordenados con la relación

TEX: $\mathcal{R}=\{(a,a')\in \mathbb{R}: a'-a \text{ es positivo o cero }\}$.

Por la ley de tricotomía y el hecho que la suma de positivos es positvo, se deduce que la relación TEX: $\mathcal{R}$ es una relación de orden en TEX: $\mathbb{R}$. Esta relación es llamada el orden creciente de los números reales y denotada por TEX: $\le$, luego TEX: $(a,a')\in \mathcal{R} \Leftrightarrow a\le a'$. Y el par TEX: $(\mathbb{R},\le)$ es un conjunto ordenado.

2) El par TEX: $(\mathbb{R},\ge)$ también es un conjunto ordenado, donde

TEX: $a\ge a'\Leftrightarrow a'\le a$.


3) El par TEX: $(\mathbb{Z}^+, |)$ es un conjunto ordenado, donde
TEX: $a|a' \Leftrightarrow a\text{ es un divisor de } a'$.


4) Sea TEX: $X$ un conjunto cualquiera, denotamos TEX: $\mathcal{P}(X)$ al conjunto de todos los subconjutos de TEX: $X$, i.e.

TEX: $\mathcal{P}(X)=\{ Y: Y\subset X \}$.

Los pares TEX: $(\mathcal{P}(X),\subset)$ y TEX: $(\mathcal{P}(X),\supset)$ son conjuntos ordenados.

5) Si el par TEX: $(A, \mathcal{R})$ es un conjunto ordenado, y TEX: $B\subset A$, entonces la relación

TEX: $\mathcal{R}'=\{(b,b')\in B\times B: b\mathcal{R} b'\}$

induce un orden en TEX: $B$ donde TEX: $b\mathcal{R}'b'\Leftrightarrow b\mathcal{R}b'$. Este nuevo orden TEX: $\mathcal{R}'$ es denotado por abuso de notación como TEX: $\mathcal{R}$.

Definción: Sea TEX: $(A,\mathcal{R})$ un conjunto ordenado. Un elemento TEX: $a\in A$ se dice minimal si

TEX: $\forall a'\in A: a'\mathcal{R}a\Rightarrow a'=a$.


Por ejemplo en el par TEX: $(\mathbb{R}_{\ge 0}, \le )$ el TEX: $0$ es el único elemento minimal. El principio de buena ordenación nos dice que todo par TEX: $(A,\le)$ donde TEX: $A\subset \mathbb{N}$ es no vacío, posee un único elemento minimal. En el conjunto ordenado TEX: $(\mathbb{Z}_{\ge 2}, |)$ un elemento es minimal si, y sólo si, es un número primo (luego hay infinitos elementos minimales). Si TEX: $X=\{0,1,2,3\}$ y TEX: $A=\{ \{0\}, \{1,2\}, \{1,3\}, \{0,1,3\}, \{3\}\}\subset \mathcal{P}(X)$, entonces los elementos minimales de TEX: $(A,\subset)$ son TEX: $\{0\}$, TEX: $\{1,2\}$ y TEX: $\{3\}$; mientras que los elementos minimales de TEX: $(A,\supset)$ son TEX: $\{1,2\}$ y TEX: $\{0,1,3\}$.

Principio Extremal: Todo conjunto ordenado finito y no vacío posee un elemento minimal.

Al igual que el principio del palomar, este principio parece sumamente obvio e inofensivo al comienzo, sin embargo tiene aplicaciones tanto o más potentes que el principio del palomar. A modo de ejemplo resolveré tres problemas:
Go to the top of the page
 
+Quote Post
Luffy
mensaje Jan 19 2015, 09:11 AM
Publicado: #2


Dios Matemático Supremo
Ícono de Grupo

Grupo: Usuario FMAT
Mensajes: 556
Registrado: 16-August 06
Desde: Rio de Janeiro
Miembro Nº: 1.950
Nacionalidad:
Colegio/Liceo: Instituto Nacional
Universidad: Instituto Nacional de Matematica Pura e Aplicada (IMPA)
Sexo:



Problema 1: Pruebe que dado un conjunto finito de TEX: $2n$ puntos en el plano, tal que no hay tres colineales. Siempre es posible trazar segmentos entre ellos, de modo de formar TEX: $n$ parejas y que ningún par de segmentos se corte.

Solución: Consideramos TEX: $X$ el conjunto de todos los posibles emparejamientos que podemos trazar entre los TEX: $2n$ puntos (sin importar si algunos segmentos se intersectan o no). Es claro que TEX: $X$ es un conjunto finito (de hecho es bien grande) y no vacío. Definimos TEX: $A\subset \mathbb{R}^+$ como

TEX: $A=\{L\in \mathbb{R}^+: \exists a\in X \text{ tal que la suma de todos los largos de los segmentos de }a \text{ es igual a }L\}$.

Como TEX: $X$ es finito no vacío, TEX: $A$ también lo es. Por el principio extremal existe TEX: $L\in A$ minimal respecto a TEX: $\le$. Es decir existe un emparejamiento TEX: $a\in X$ tal que la suma de los largos de los segmentos es minimal. Si suponemos que en este emparejamiento TEX: $a$ hay segmentos que se cortan, digamos TEX: $\overline{AB}$ y TEX: $\overline{CD}$ se cortan en TEX: $P$, entonces si consideramos el emparejamiento TEX: $a'$ que es igual a TEX: $a$ excepto en los puntos TEX: $A$, TEX: $B$, TEX: $C$ y TEX: $D$, donde en lugar de emparejar TEX: $\overline{AB}$ y TEX: $\overline{CD}$, emparejamos TEX: $\overline{AC}$ y TEX: $\overline{BD}$, tenemos que

TEX: \begin{center}<br />$l(AB)+l(CD)=l(AP)+l(PB)+l(CP)+l(PD)=l(AP)+l(PC)+l(BP)+l(PD)>l(AC)+l(BD)$<br />\end{center}

entonces si TEX: $L'$ es la suma de los largos de los segmentos de TEX: $a'$ tenemos que TEX: $L'< L$ lo que contradice la minimalidad de TEX: $L$. De esta forma concluimos que nuestra suposición es imposible, es decir el emparejamiento TEX: $a$ es tal que ningún par de segmentos se cortan. TEX: $\blacksquare$

Problema 2: (Korea, 1995) Considere una cantidad finita de puntos en el plano tales que, si elegimos tres puntos
de ellos TEX: $A$, TEX: $B$ y TEX: $C$, el área del triángulo TEX: $ABC$ es siempre menor a TEX: $1$. Pruebe que existe un triángulo de área menor a TEX: $4$, tal que todos los puntos están en el interior o el borde de este triángulo.

Solución: Sea TEX: $X$ el conjunto de todos los triángulos que pueden ser formados con estos puntos. TEX: $X$ es finito y no vacío. Consideremos TEX: $Y\subset \mathbb{R}$ el conjunto de todas las áreas de los triángulos de TEX: $X$. Por el principio extremal aplicado a TEX: $(Y,\ge)$ existen tres puntos TEX: $a$, TEX: $b$ y TEX: $c$ del cunjunto finito de puntos, tales que el triángulo formado por ellos tiene la mayor área posible en TEX: $Y$. De esta forma, si TEX: $d$ es cualquier otro de los puntos dados, tenemos que respecto a TEX: $ab$, la altura de TEX: $d$ es menor o igual que la de TEX: $c$, es decir, TEX: $d$ está entre las dos rectas paralelas a TEX: $ab$ cuya distancia de TEX: $ab$ es igual a la distancia de TEX: $c$ a TEX: $ab$, es decir, está entre la recta TEX: $L_1$ que es paralela a TEX: $ab$ y que pasa por TEX: $c$ y su reflexión respecto a TEX: $ab$. Analogamente concluimos que TEX: $d$ está entre la recta TEX: $L_2$ paralela a TEX: $bc$ pasando por TEX: $a$ y su reflexión respecto a TEX: $bc$, y que también está entre la recta TEX: $L_3$ paralela a TEX: $ca$ que pasa por TEX: $b$ y su reflexión respecto a TEX: $ca$. Es decir, TEX: $d$ cae dentro del triángulo formado por las rectas TEX: $L_1$, TEX: $L_2$ y TEX: $L_3$, que llamaremos TEX: $ABC$, es fácil ver que el área del triángulo TEX: $ABC$ es cuatro veces el área del triángulo TEX: $abc$, y como este último tiene área menor a TEX: $1$, concluimos que TEX: $ABC$ tiene área menor a TEX: $4$. TEX: $\blacksquare$

Problema 3: Encuentre todas las soluciones enteras de la ecuación TEX: $x^2+y^2=3z^2$.

Solución: Primero observamos que si TEX: $z=0$ necesariamente TEX: $x=y=0$. Veremos que esta es la única solución. Supongamos por contradicción que existe una solución tal que TEX: $z\neq 0$. Llamemosle a dicha solución TEX: $(x_0,y_0,z_0)$. Sea

TEX: $A=\{n\in\mathbb{Z}^+: n=z^2, \text{ donde }z^2\le z_0^2\text{ y } 3z^2\text{ se escribe como suma de dos cuadrados perfectos}\}$.

Claramente TEX: $A$ es finito y es no vacío pues TEX: $|z_0|\in A$. Por el principio extremal, existe TEX: $z_1\in A$ minimal con respecto al orden TEX: $|$. Luego existen TEX: $x_1,y_1\in\mathbb{Z}$ tales que TEX: $x_1^2+y_1^2=3z_1^2$. Mirando los restos cuadráticos en módulo TEX: $4$, vemos que la única opción de que se cumpla la igualdad es que los tres números sean pares, es decir TEX: $x_1=2x_2$, TEX: $y_1=2y_2$ y TEX: $z_1=2z_2$. Luego tendremos que TEX: $x_2^2+y_2^2=3z_ 2^2$, entonces TEX: $z_2\in A$ con TEX: $z_2|z_1$ y TEX: $z_2\neq z_1$. Esto contradice la minimalidad de TEX: $z_1$. TEX: $\blacksquare$

Les dejo links de problemas que pueden ser resueltos con este principio:

- Video del clásico problema de Sylvester https://www.youtube.com/watch?v=C-F3zpdiv5U
- P5 de http://www.fmat.cl/index.php?showtopic=90279
- P5 de http://www.fmat.cl/index.php?showtopic=90311
- P1 de http://www.fmat.cl/index.php?showtopic=2150
- http://www.fmat.cl/index.php?showtopic=90259
- http://www.fmat.cl/index.php?showtopic=90963
- P6 de http://www.fmat.cl/index.php?showtopic=28251
- P6 de http://www.fmat.cl/index.php?showtopic=53403
- P6 de http://www.fmat.cl/index.php?showtopic=954
- P3 de http://www.fmat.cl/index.php?showtopic=11187&st=0

Saludos

Mensaje modificado por Luffy el Jan 20 2015, 06:36 AM
Go to the top of the page
 
+Quote Post
 

Reply to this topicStart new topic
1 usuario(s) está(n) leyendo esta discusión (1 invitado(s) y 0 usuario(s) anónimo(s))
0 miembro(s):

 

Versión Lo-Fi Fecha y Hora actual: 16th June 2025 - 01:57 AM
Powered By IP.Board 2.2.1 © 2007  IPS, Inc.