Archivo de la etiqueta: tablero

Seminario de Resolución de Problemas: Principio de las Casillas, Parte 2

Continuamos con ejemplos de aplicación del principio de las casillas

PROBLEMA 5. Sean a_1, a_2, ... , a_n números enteros, no necesariamente todos diferentes. Prueba que existe un subconjunto de estos números, tal que su suma es divisible por n.

Solución. Consideremos los números s_1, s_2,..., s_n los cuales definimos como sigue

s_1=a_1
s_2=a_1+a_2
s_3=a_1+a_2+a_3

s_n=a_1+a_2+ ... +a_n

Tenemos que al dividir cada s_i entre n tenemos que el residuo varía de 0 a n-1. Si el residuo es 0 ya acabamos. Por otro lado, si ninguno de los residuos es cero, por el principio de las casillas tenemos que deben de existir al menos dos de los s_i´s que tengan el mismo residuo. Supongamos que son s_j y s_k con j<k.

Como s_j y s_k tienen el mismo residuo, tenemos que s_k-s_j es divisible por n. Así el conjunto S=\{s_{j+1}, s_{j+2}, \ldots , s_k \} es el conjunto tal que la suma de sus elementos es divisible por n.

\square

PROBLEMA 6.  Cada cuadrito de un tablero de ajedrez de 4×7 es coloreado de blanco o negro. Prueba que en cualquier coloración siempre hay un rectángulo del tablero que tiene los cuatro cuadritos de las esquinas coloreadas del mismo color.

Solución. Podemos reducir el problema a un tablero de 3×7, dado que cualquier rectángulo que se pueda crear en un tablero de 3×7, también será un rectángulo en el tablero original. Ahora bien, pensemos en las posibles coloraciones que puede tener una columna en el tablero de 3×7. Son dos colores acomodados en 3 lugares, así que tenemos 8 acomodos diferentes de coloración: BBB, BBN, BNB, NBB, BNN, NBN, NNB, NNN.

Notemos que si dos columnas tienen el mismo acomodo de colores, entonces acabamos (por ejemplo, dos columnas BNB hacen un rectángulo de cuatro esquinas blancas).

Supongamos que usamos la coloración BBB en una columna. Si en otra columna pintamos con alguno de BBB, BBN, BNB, NBB, entonces acabamos (usando dos de la BBB y dos de esa otra). Si no, es que en las seis columnas restantes pintamos sólo con acomodos BNN, NBN, NNB, NNN. Por principio de las casillas, hay dos columnas pintadas con el mismo acomodo, y terminamos. Por simetría, si usamos la coloración NNN entonces podemos hacer un argumento análogo.

Ya sólo nos quedan los casos en los que ninguna columna queda pintada ni con BBB ni con NNN. Pero entonces tenemos que pintar las 7 columnas con 6 acomodos posibles. Por principio de las casillas, hay dos columnas que quedan pintadas con el mismo acomodo, y como ya vimos, esto crea el rectángulo con esquinas del mismo color.

\square

PROBLEMA 7. Si seleccionamos n + 1 enteros del conjunto \{1, 2, \ldots 2n\}, siempre hay dos de ellos tales que su máximo común divisor es 1.

Solución. Tomemos al conjunto \{1, 2, \ldots, 2n\}. Si al tomar n+1 de ellos siempre logramos encontrar dos consecutivos, entonces el problema estará resuelto, ya que cualesquiera dos consecutivos son primos relativos. A la hora que seleccionamos n+1 enteros del conjunto dado, tenemos por el principio de casillas que al menos dos de ellos serán consecutivos. En efecto, dividamos a los números en las parejas \{1,2\}, \{3,4\}, \ldots, \{2n-1,2n\}. Estas son n parejas, así que por casillas hubo una pareja de la que elegimos dos números. Estos son dos números consecutivos, así que que su máximo común divisor es 1.

\square

PROBLEMA 8. En una grafo con un número finito de vértices, hay dos vértices con el mismo grado.

Solución. Sea n el número de vértices de la gráfica, dado que el grado del vértice de un grafo es el número de aristas que concurren en dicho vértice. Tenemos que el grado de cada vértice varía de 0 a n-1. Sin embargo si un vértice tiene grado cero, no existirá algún vértice con grado n-1. Por el principio de las casillas teniendo en cuenta que tenemos que distribuir n-1 valores en n lugares, concluimos que al menos dos de los vértices deben de tener el mismo grado.

\square

Busca una contradicción

HeuristicasTerminamos esta serie de técnicas de resolución de problemas con una de las técnicas más finas y más usadas en las matemáticas: las pruebas por contradicción.

La idea es la siguiente. Por un momento suponemos que lo que queremos demostrar es falso. Después trabajaremos haciendo todo lo demás correctamente. La idea es llegar a una contradicción con las hipótesis del problema, o bien a algo que sabemos que es imposible. De esta forma, sabemos que debe haber un error en la demostración de eso imposible. Y como lo único que hicimos mal fue suponer que lo original era falso, debemos tener que en realidad es verdadero.

En estos videos veremos varios ejemplos de este argumento para acostumbrarnos. Es súper útil pensar en estos argumentos casi automáticamente.

Ir a los videos…

Generalizar el problema

HeuristicasA veces tener un problema concreto es más difícil que tener un problema más general. En los problemas concretos puede haber números grandes, o un brinco muy difícil, o bien simplemente no existen herramientas para atacarlo por separado. Cuando generalizamos podemos aprovechar más teoría, por ejemplo el principio de inducción.

En estos videos veremos algunos ejemplos en los cuales es más fácil resolver un problema que aparentemente debería de ser más difícil.

Ir a los videos…

Aprovechar la simetría

HeuristicasLa simetría, además de ser una propiedad que hace que las cosas se vean bonitas, también es una buena técnica de resolución de problemas. Hay varias formas en las que se puede aprovechar la simetría en un problema. Una es para reducir esfuerzo: ¿para qué repetir un argumento si es el mismo? ¿para qué desarrollar todos los términos si la ecuación es simétrica?

En  otras ocasiones la simetría nos permite sospechar que los casos especiales tienen que ser simétricos. A veces no hay razón para que sea de otra forma. Finalmente, la simetría también está presente en una gran variedad de la información del problema, y hay que inventarla o descubrirla para simplificar cuentas, notación y conjeturas.

Ir a los videos…