Principio del Mínimo

Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 563
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Principio del Mínimo

Mensaje sin leer por Nacho »

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]
2  
"Though my eyes could see I still was a blind man"
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024
Mensajes: 486
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 2
Nivel: 3
Contactar:

Re: Principio del Mínimo

Mensaje sin leer por drynshock »

¿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}}$
Juaco

OFO - Medalla de Bronce-OFO 2020 OFO - Mención-OFO 2021 OFO - Medalla de Bronce-OFO 2022
Mensajes: 230
Registrado: Jue 10 Oct, 2019 8:24 pm
Medallas: 3
Ubicación: Uruguay

Re: Principio del Mínimo

Mensaje sin leer por Juaco »

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."}$
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Principio del Mínimo

Mensaje sin leer por Joacoini »

Juaco escribió: Mié 13 Dic, 2023 7:07 pm
drynshock escribió: Mié 13 Dic, 2023 12:41 am ¿Que significa la "o" rara de la ultima solución?
si 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$
Normalmente es eso, pero acá Nacho esta usando $\sigma$ para escribir la suma de dígitos de un número.
NO HAY ANÁLISIS.
Responder