miércoles, 29 de mayo de 2013

Problema del día (29-05-2013) (Chiu)

El conteo doble es una de las técnicas más útiles en problemas de combi y puede ser de mucha ayuda al probar desigualdades entre cosas que hay que contar. Aquí van dos problemas:

$a)$ En un tablero rectangular de $m\times n$, dos casillas son adyacentes si comparten un lado, y un camino es una sucesión de casillas donde cada dos casillas consecutivas son adyacentes. Cada casilla se colorea de blanco o negro. Sea $N$ la cantidad de coloraciones del tablero tales que en ellas existe al menos un camino de puras casillas negras que va del extremo izquierdo al extremo derecho del tablero. Sea $M$ la cantidad de coloraciones del tablero tales que en ellas existen al menos dos caminos de puras casillas negras que no se intersecan (es decir, que no tienen casillas en común), donde cada uno de estos caminos va del extremo izquierdo al extremo derecho del tablero. Demuestra que $N^{2}\geq 2^{mn}M$.

$b)$ Un fotógrafo tomó $10$ fotografías. En cada fotografía hay $3$ personas: un hijo a la izquierda, su padre al centro, y un hermano de su padre (tío) a la derecha (todos hombres). Las $10$ personas que están al centro de las fotografías son todas distintas. Si $n$ es el número de personas que aparecen en al menos una fotografía, demuestra que $n\geq 16$.

9 comentarios:

Juan dijo...

(b) ¿Puede haber incesto? ¿Medios hermanos (medio tío)? ¿Que alguien y su hermano tengan un hijo juntos? ¿Todos deben ser hombres?

Enrique dijo...

No Juan, todos son hombres, y no cuentan adopciones. No hay medios hermanos tampoco.

Unknown dijo...

En el primer problema, las $M$ coloraciones de tableros son tales que los caminos ajenos

1. no tienen casillas negras adyacentes
2. o simplemente no tienen casillas negras en común?

Enrique dijo...

Los caminos ajenos son los que no tienen casillas negras en común.

Enrique dijo...

¿Quieren un hint?

Juan dijo...

No. La verdad no he podido trabajarlos casi nada.

Juan dijo...

(a) Considero las parejas de tableros (A,B) y (C.D) donde:
-> A tiene al menos un camino bueno
-> B tiene al menos un camino bueno
-> C es un tablero cualquiera
-> D tiene dos caminos buenos.

Si tomo el camino más chaparrito en D, le llamo X al conjunto de cuadritos en ese camino, o más abajo. Ahora, intercambio las regiones X de los tableros C y D. Obtengo (C', D').

Es fácil ver que esta operación es una inyección de las parejas tipo (C,D) (hay $2^{mn}M$ de ellas), y las parejas tipo (A,B) (hay $N^2$) de ellas. Entonces acabo.

Enrique dijo...

Bien, está padre la idea de considerar parejas de tableros y comparar las cantidades.

El problema a) es el C3 del 2005, por si quieren checarlo.

Enrique dijo...

Hint para el problema b):
Pbafvqrene tehcbf qr ureznabf l pbagne pháagbf unl.

(el texto está en http://www.rot13.com/ , para descifrarlo nada más cópienlo)

Publicar un comentario