Principio del Mínimo
Principio del Mínimo
Cuando tenemos que enfrentar un problema, siempre está bueno poder observar situaciones límites. O sea, ver qué pasa con los casos chicos, cuando me acerco al menor valor posible, al mayor, etc.
El principio del mínimo dice que todo subconjunto no vacío [math] del conjunto de los enteros positivos [math] tiene un elemento mínimo.
Demostrar algo mediante el principio del mínimo es una prueba del estilo de reducción al absurdo: se trata de suponer que [math] es el menor número para el cual se tiene una propiedad [math], y luego, se encuentra un [math] tal que [math] tiene la propiedad [math], entonces se cumple [math].
Problemas Relacionados
Vamos a ver un par de problemas que se resuelven con esta idea:
Problema 1:
En el plano se marcaron [math] puntos: [math] rojos y [math] azules. Demostrar que es posible trazar [math] segmentos que unan, cada uno, un punto rojo con uno azul, y que ningún par de segmentos tengan puntos en común.
Solución
Es claro que la cantidad de configuraciones tales que se une un punto rojo con uno azul es finita. Luego, podemos tomar la configuración [math] tal que la suma de los segmentos sea mínima. Supongamos que en [math] se cruzan dos segmentos [math] y [math] en algún punto, con [math] y [math] rojos y [math] y [math] azules. Podemos cambiar los segmentos [math] y [math] por [math] y [math] respectivamente. Pero tenemos que, en cualquier cuadrilátero convexo, la suma de las diagonales es mayor que la dos lados opuestos. Luego [math]. Así encontramos una configuración [math] cuya suma de los segmentos es menor que la de [math]. Absurdo, puesto que la de [math] era mínima. Luego, [math] no tiene cruzamientos. [math]
Problema 2:
En un país hay varias provincias y en algunas de ellas hay una persona. Cada mes, una persona viaja a una provincia vacía en la que no haya estado antes. Luego de algunos años, cada persona visitó todas las provincias y volvío a su provincia original. Probar que en algún momento ninguna persona estuvo en su provincia.
Solución:
Sea [math] la persona que vuelve primero a su provincia, tras [math] meses. En el mes [math], podemos ver que no había nadie en su provincia, ya que, como [math] visitó todas las otras provincias, cada persona debe haber viajado de su provincia, y nadie regresó ya que [math] es el primero que regresa. Luego en el mes [math] nadie está en su provincia original. [math]
Problema 3:
Probar que la ecuación [math] no tiene soluciones en los enteros positivos.
Solución:
Supongamos que existe alguna solución, y sea esta la terna [math] con [math] mínimo. Mirando la ecuación módulo [math], tenemos que [math]. Pero como [math], tenemos que [math] y [math]. Reemplazamos [math], [math]. La ecuación original pasa a ser [math], que es lo mismo que [math], de donde [math]. Reemplazamos [math], y obtenemos [math], que es lo mismo que [math]. Luego, si [math] es solución [math] es solución. Pero tenemos que [math]. Absurdo, ya que [math] es mínimo. Entonces la ecuación no tiene solución en enteros positivos. [math]
Problema 4:
Sea [math] un entero positivo y [math] el número formado por [math] dígitos [math]: [math]. Si [math] es un múltiplo de [math], determinar el menor valor que puede tener la suma de los dígitos de [math].
Solución:
Vamos a demostrar que si [math] es un múltiplo de [math], luego, la suma de los dígitos de [math] es al menos [math].
Para ello, procederemos por el absurdo: supongamos que existen múltiplos de [math] que tienen la suma de los dígitos menor que [math] y llamemos [math] al menor de estos múltiplos. [math] puesto que es múltiplo de [math] y los múltiplos de [math] de [math] digitos son de la forma [math], y se ve claramente que la suma de sus cifras es mayor que [math].
Entonces, [math] con [math]
Hacemos una manipulación algebraica: [math]
[math].
Luego, [math] es un múltiplo de [math].
La suma de las cifras de [math] es [math], ya que [math]. Pero [math]. Luego, tenemos que [math].
Tenemos una conocida desigualdad que dice que [math]. Luego, la suma de las cifras de [math] es menor que la suma de las cifras de [math]. Absurdo, puesto que [math] era el menor múltiplo de [math] con la menor suma de cifras.
Entonces, la suma de las cifras va a ser siempre mayor o igual a [math]. [math]
El principio del mínimo dice que todo subconjunto no vacío [math] del conjunto de los enteros positivos [math] tiene un elemento mínimo.
Demostrar algo mediante el principio del mínimo es una prueba del estilo de reducción al absurdo: se trata de suponer que [math] es el menor número para el cual se tiene una propiedad [math], y luego, se encuentra un [math] tal que [math] tiene la propiedad [math], entonces se cumple [math].
Problemas Relacionados
Vamos a ver un par de problemas que se resuelven con esta idea:
Problema 1:
En el plano se marcaron [math] puntos: [math] rojos y [math] azules. Demostrar que es posible trazar [math] segmentos que unan, cada uno, un punto rojo con uno azul, y que ningún par de segmentos tengan puntos en común.
Solución
Es claro que la cantidad de configuraciones tales que se une un punto rojo con uno azul es finita. Luego, podemos tomar la configuración [math] tal que la suma de los segmentos sea mínima. Supongamos que en [math] se cruzan dos segmentos [math] y [math] en algún punto, con [math] y [math] rojos y [math] y [math] azules. Podemos cambiar los segmentos [math] y [math] por [math] y [math] respectivamente. Pero tenemos que, en cualquier cuadrilátero convexo, la suma de las diagonales es mayor que la dos lados opuestos. Luego [math]. Así encontramos una configuración [math] cuya suma de los segmentos es menor que la de [math]. Absurdo, puesto que la de [math] era mínima. Luego, [math] no tiene cruzamientos. [math]
Problema 2:
En un país hay varias provincias y en algunas de ellas hay una persona. Cada mes, una persona viaja a una provincia vacía en la que no haya estado antes. Luego de algunos años, cada persona visitó todas las provincias y volvío a su provincia original. Probar que en algún momento ninguna persona estuvo en su provincia.
Solución:
Sea [math] la persona que vuelve primero a su provincia, tras [math] meses. En el mes [math], podemos ver que no había nadie en su provincia, ya que, como [math] visitó todas las otras provincias, cada persona debe haber viajado de su provincia, y nadie regresó ya que [math] es el primero que regresa. Luego en el mes [math] nadie está en su provincia original. [math]
Problema 3:
Probar que la ecuación [math] no tiene soluciones en los enteros positivos.
Solución:
Supongamos que existe alguna solución, y sea esta la terna [math] con [math] mínimo. Mirando la ecuación módulo [math], tenemos que [math]. Pero como [math], tenemos que [math] y [math]. Reemplazamos [math], [math]. La ecuación original pasa a ser [math], que es lo mismo que [math], de donde [math]. Reemplazamos [math], y obtenemos [math], que es lo mismo que [math]. Luego, si [math] es solución [math] es solución. Pero tenemos que [math]. Absurdo, ya que [math] es mínimo. Entonces la ecuación no tiene solución en enteros positivos. [math]
Problema 4:
Sea [math] un entero positivo y [math] el número formado por [math] dígitos [math]: [math]. Si [math] es un múltiplo de [math], determinar el menor valor que puede tener la suma de los dígitos de [math].
Solución:
Vamos a demostrar que si [math] es un múltiplo de [math], luego, la suma de los dígitos de [math] es al menos [math].
Para ello, procederemos por el absurdo: supongamos que existen múltiplos de [math] que tienen la suma de los dígitos menor que [math] y llamemos [math] al menor de estos múltiplos. [math] puesto que es múltiplo de [math] y los múltiplos de [math] de [math] digitos son de la forma [math], y se ve claramente que la suma de sus cifras es mayor que [math].
Entonces, [math] con [math]
Hacemos una manipulación algebraica: [math]
[math].
Luego, [math] es un múltiplo de [math].
La suma de las cifras de [math] es [math], ya que [math]. Pero [math]. Luego, tenemos que [math].
Tenemos una conocida desigualdad que dice que [math]. Luego, la suma de las cifras de [math] es menor que la suma de las cifras de [math]. Absurdo, puesto que [math] era el menor múltiplo de [math] con la menor suma de cifras.
Entonces, la suma de las cifras va a ser siempre mayor o igual a [math]. [math]
"Though my eyes could see I still was a blind man"
Re: Principio del Mínimo
¿Que significa la "o" rara de la ultima solución?
@Bauti.md ig // Ridin' in a getaway car // $\zeta (s) =\displaystyle\sum_{n = 1}^{\infty}\frac{1}{n^{s}}$
Re: Principio del Mínimo
bueno, mala mía. ahí abajo @Joacoini me corrigió y explica lo que es, tendría que haber leído la solución antes jajaja perdón.
Última edición por Juaco el Mié 13 Dic, 2023 10:51 pm, editado 1 vez en total.
$\text{“The further removed from usefulness or practical application, the more important."}$
-
Joacoini
- Mensajes: 460
- Registrado: Jue 12 Oct, 2017 10:17 pm
- Medallas: 16
- Nivel: Exolímpico
- Ubicación: Ciudad Gotica
Re: Principio del Mínimo
Normalmente es eso, pero acá Nacho esta usando $\sigma$ para escribir la suma de dígitos de un número.Juaco escribió: ↑Mié 13 Dic, 2023 7:07 pmsi te referís a ésta "o rara": $\sigma$, es la función $\text{sigma}$, que cuenta los divisores de un número. o sea $\sigma(x)$ es la cantidad de divisores de $x$.
por ejemplo:
$\sigma(12)=6$ porque los divisores de $12$ son $1; 2; 3; 4; 6; 12$
o también, si tenemos un número primo $p$, por definición de un número primo se dá que (p)=2$
NO HAY ANÁLISIS.