Archivo de la etiqueta: casillas

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$

Seminario de Resolución de Problemas: Principio de las Casillas

Esta es una serie de entradas de blog para dar seguimiento a los estudiantes del Seminario sobre Enseñanza de las Matemáticas (Resolución de Problemas) durante la época de cuarentena debida al coronavirus.

Introducción

Imaginemos que tenemos un botiquín con $9$ espacios para acomodar medicamentos. Si contamos con un total de $10$ medicamentos para acomodar en los $9$ espacios, es claro pensar que al menos uno de los $9$ espacios tendrá al menos $2$ medicamentos. Eso lo podemos deducir a partir de que no hay posibilidad de repartir los $10$ medicamentos de manera equitativa en los $9$ espacios, ya que tenemos más objetos que acomodar que lugares en donde distribuir.

Siguiendo el ejemplo anterior, podemos generalizar un poco. Si tuviésemos $n$ lugares en el botiquín y $n+1$ medicamentos, podemos concluir lo mismo: al menos en una casilla habría más de un medicamento.

El esquema propuesto anteriormente es un versión básica del principio de casillas. Si volvemos a nuestro problema inicial, con el botiquín con $9$ lugares disponibles, pero ahora tenemos un total de $19$ medicamentos, de igual manera, no podemos distribuir los medicamentos de manera equitativa en los nueve lugares, y ahora si lo pensamos con un poco más de detalle, podemos concluir que en alguna de las $9$ casillas deberían de haber al menos $3$ medicamentos. Esto surge en consecuencia de pensar que podemos distribuir de manera equitativa los $19$ medicamentos en los $9$ lugares, sin embargo si colocamos en cada lugar un total de $2$ medicamentos, tendríamos que hemos acomodado un total de $18$ ($9\times 2$) medicamentos, quedándonos $1$ medicamento por acomodar, el cual debería de ir en alguno de los lugares con $2$ medicamentos cada uno. Con esto concluimos que en alguno de los lugares del botiquín debe de haber al menos $3$ medicamentos.

Con lo anterior, enunciaremos el principio de casillas.

Principio de Casillas: Si se distribuyen al menos $\textbf{nk+1}$ elementos en $\textbf{n}$ lugares, se tiene que uno de esos lugares tiene al menos $\textbf{k+1}$ elementos.

Este principio puede ser de gran utilidad para la resolución de problemas en los cuales hay que exhibir la existencia de elementos que cumplen cierta propiedad.

Problemas

A continuación veremos ciertos problemas en los que se muestra que el principio de las casillas es una herramienta poderosa para su resolución.

Problema 1. Demuestre que si hay $n$ personas en una fiesta, entonces dos de ellos conocen la misma cantidad de personas (entre los presentes).

Solución. Supongamos que hay una persona $P$ que no conoce a ninguna de las $n-1$ personas restantes. Cada una de las personas en la fiesta conoce a un número de personas entre un rango de $0$ a $n-2$ (nadie puede conocer a los $n-1$ restantes pues nadie puede conocer a $P$)Ahora, aplicando el principio de casillas, relacionando a cada persona su número de conocidos, el cual varía de $0$ a $n-2$, tenemos que al menos dos personas deben de conocer el mismo número de personas.

De igual manera, si suponemos que toda persona conoce a alguien, tenemos que el número de conocidos de cada persona varía de $1$ a $n-1$. Aplicando de nueva cuenta el principio de casillas, al asociar a cada persona su número de conocidos, tenemos que al menos dos se repiten.

$\square$

Problema 2: Dado un conjunto de $n+1$ enteros positivos, todos ellos menores o iguales a $2n$, muestra que al menos un miembro del conjunto debe dividir a otro miembro del conjunto.

Solución. Sean $a_1, a_2, …, a_{n+1}$ dichos enteros positivos. Al factorizar la máxima potencia de dos que divide a cada uno de ellos, podemos escribir a cada número de la forma $a_i=2^{m_i}·b_i$ de tal forma que $b_i$ es un número impar mayor o igual que uno y $m_i$ es un entero no negativo. Consideramos a $B$ como el conjunto de todos los $b_i$´s $$B=\lbrace b_1, b_2, …, b_{n+1}\rbrace.$$

Tenemos que entre $1$ y $2n$ hay un total de $n$ números impares, así que en el conjunto $B$ debe de haber dos elementos que sean iguales entre sí. Supongamos que $b_i$ y $b_j$ son dichos elementos. Con ello, si $m_i\leq m_j$ entonces $a_i$ divide a $a_j$. Y si $m_i>m_j$ entonces $a_j$ divide a $a_i$.

$\square$

Problema 3: Dados los puntos A, B, C, D, E al interior de un cuadrado unitario, demuestra que al menos hay dos puntos cuya distancia es menor a $\frac{\sqrt{2}}{2}$.

Solución. Si dividimos el cuadrado en $4$ cuadrados iguales, tenemos que por el principio de casillas en al menos uno de los cuadrados debe de haber $2$ puntos. Sin perdida de generalidad, supongamos que  A y B son dichos puntos que quedan la interior de uno de estos cuadrados pequeños. Tenemos que le diagonal del cuadrado pequeño es $\frac{\sqrt{2}}{2}$, es por ello que cualesquiera dos puntos al interior del cuadrado pequeño estarán distanciados menos que $\frac{\sqrt{2}}{2}$.

$\square$

Problema 4. Prueba que una línea recta que no pasa por uno de los vértices de un triángulo, no puede cortar los tres lados del triángulo.

Solución. Tenemos que una recta divide al plano en dos regiones. Si tomamos estas regiones como «casillas» tenemos que en una de nuestras casillas hay al menos dos puntos del triángulo los cuales forman un segmento de recta que es uno de los lados del triángulo. Con esto tenemos que la recta no corta ese lado del triángulo.

$\square$

Puedes dejar dudas de la entrada o soluciones alternativas a algunos de estos problemas aquí abajo en los comentarios.

Más ejemplos

Puedes encontrar más ejemplos en la Sección 2.6 del Larson, o en la siguiente entrada que escribiremos al respecto.