COFFEE: "Matías Saucedo" - Problema 2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
COFFEE
Mensajes: 33
Registrado: Vie 13 Mar, 2020 7:19 pm
Nivel: Exolímpico

COFFEE: "Matías Saucedo" - Problema 2

Mensaje sin leer por COFFEE » Sab 14 Mar, 2020 12:00 am

Se tienen $n$ rectas en el plano que lo dividen en regiones. Supongamos que no hay tres de estas rectas que pasan por el mismo punto. Probar que se puede colorear con dos colores las regiones de manera que cualesquiera dos de ellas adyacentes sean de distintos colores.
1  

Avatar de Usuario
COFFEE
Mensajes: 33
Registrado: Vie 13 Mar, 2020 7:19 pm
Nivel: Exolímpico

Re: COFFEE: "Matías Saucedo" - Problema 2

Mensaje sin leer por COFFEE » Lun 16 Mar, 2020 11:38 pm

Solución Oficial:
Spoiler: mostrar
Vamos a hacer inducción sobre $n$. Como caso base consideramos $n=1$, tenemos entonces una única recta que divide al plano en dos semiplanos, coloreamos uno de ellos de negro y el otro de blanco, como esto cumple lo pedido por el enunciado, el caso base está resuelto.
Supongamos como hipótesis inductiva que el enunciado es cierto para $n=k$ rectas. Veamos entonces que el enunciado es cierto para $k+1$ rectas.
Tenemos $k+1$ rectas en el plano de forma que no hay tres que pasan por un mismo punto, ignoremos por un momento una de ellas (que llamaremos $\ell$ y pintaremos de rojo). Nos quedan entonces $k$ rectas tales que no hay tres que pasan por un mismo punto, luego, por la hipótesis inductiva podemos colorear de blanco y negro las regiones del plano que determinan estas $k$ rectas de manera que dos regiones adyacentes tengan colores distintos. Veamos qué pasa cuando agregamos otra vez la recta $\ell$.
Recta L.png
De nuevo, nos divide al plano en dos semiplanos, y las únicas regiones que no cumplen que todas las adyacentes a ella están pintadas del otro color son las que se forman al agregar $\ell$ (es decir, las que forman parte de una de las regiones anteriores que fueron atravesadas por $\ell$), a las que llamamos regiones partidas, que son adyacentes a una única región de su mismo color. Tomemos uno de los semiplanos determinado por $\ell$ y cambiemos el color de todas sus regiones, las que eran blancas pasan a ser negras, y las que eran negras pasan a ser blancas. De esta forma, las dos partes de cada región partida son de distinto color, y en cada semiplano se sigue cumpliendo que dos regiones adyacentes tienen distinto color. Como las únicas regiones que son adyacentes a una región del otro semiplano son las regiones partidas, pudimos colorear el plano como se pedía. Entonces el enunciado es cierto para $k+1$ rectas.
Esto completa la inducción, por lo que el problema es cierto para cualquier número $n$ de rectas, y con eso terminamos.
Nueva coloración.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-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
Mensajes: 259
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: COFFEE: "Matías Saucedo" - Problema 2

Mensaje sin leer por BrunZo » Mar 17 Mar, 2020 12:18 am

Grandioso.
Spoiler: mostrar
Como no me gusta la inducción, vamos a usar otra idea.

Supongamos que cada región tiene un contador, que inicia en $0$.
Para cada recta $l$, que divide al plano en dos semiplanos, elegimos uno de estos semiplanos y para cada región que pertenece al semiplano elegido le sumamos $1$ a su contador. Al finalizar, a cada región cuyo contador muestre un número impar, la coloreamos de negro, y a las otras las dejamos blancas.
Ahora bien, si dos regiones son adyacentes, es claro que existe una y sólo una recta que las separa (quizás no tan obvio, pero lo suficiente), luego su contador sólo se diferencia en $1$ (lo que aporta esta recta), por lo que tienen colores distintos.
3  

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020
Mensajes: 20
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 3
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: COFFEE: "Matías Saucedo" - Problema 2

Mensaje sin leer por Fedex » Mar 17 Mar, 2020 12:35 am

Lo amé <3
Spoiler: mostrar
Veamos que lo que propone el ejercicio es posible para $n=1$
lol.png
Por lo que esta coloración puede lograrse con un cierto valor $n$ de rectas en el plano.
Ahora veamos que en caso de que poder conseguirse una coloración de regiones con $n$ rectas, puede conseguirse una coloración con $n+1$ rectas.
Supongamos que tenemos un plano con $n$ rectas que está coloreado debidamente.
cacota fc.png
Tracemos sobre este una nueva recta $R$, que dividirá al plano en 2 semiplanos, "$A$" y "$B$"
cacota fc.png
Notemos que ahora la coloración previa es invalida ya que esta recta $R$ secciona en $2$ sub-regiones nuevas a toda región por la que pasa y, como cada región estaba pintada de algún color previamente, estos pares de sub-regiones que se forman (que son adyacentes la una a la otra) aparecen pintadas del mismo color.

Pero notemos esto, si observamos individualmente a cada semiplano, es claro que estos están debidamente coloreados (ya que partimos de una coloración valida), por lo que si rotamos los colores en alguno de ellos, es decir, toda región pintada de rojo pasa a estar pintada de azul y viceversa, la coloración que se forma dentro del semiplano es valida también.
Tomemos sin perdida de generalidad al semiplano $A$ y rotemos sus colores.
cacota fc.png
Por lo que acabo de explicar cada semiplano por si solo permanece bien coloreado, pero veamos que es lo que pasa ahora en su "frontera", la recta $R$ y las sub-regiones que delimita.
Cada sub-región que delimita $R$ aparece comprendida en un semiplano, mientras que su sub-región vecina aparece comprendida en el semiplano opuesto. Antes de que rotemos los colores en $A$ cada par de sub-regiones aparecían pintadas del mismo color. Pero como ahora rotamos los colores en $A$ y no los rotamos en $B$, cada pareja de sub-regiones adyacentes tiene ahora a una sub-región pintada de un color y a otra pintada del otro.
Por lo que de esta forma cada semiplano tiene una coloración valida y la "frontera que los une" también, por lo que el plano en general admite una coloración valida con $n+1$ rectas y estamos.

En consecuencia, como puede lograrse con $n=1$ y, de lograrse con $n$ rectas, podemos llegar a una coloración con $n+1$ rectas, la coloración puede consiguirse para todo valor de $n$ rectas en el plano.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
3  
$\frac{9}{1^2} \binom{20}{18}$

Responder