Archivo de la etiqueta: casillas

Álgebra Superior I: Cardinalidad de conjuntos finitos

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

¿Qué es lo que entiendes cuando alguien te dice: «En esta canasta hay cinco manzanas»? Probablemente te llegue a la mente una imagen similar a la siguiente:

Y es que para nosotros es muy natural el decir «cuántas» cosas hay dentro de un conjunto. De hecho los primeros usos que dieron lugar al nacimiento de las matemáticas datan de hace más de $5000$ años en mesopotamia con los primeros sistemas para contar. Esto remarca la necesidad de contar objetos que a su vez trata de diferenciar unos de otros.

Imagínate que te pidieran contar cuántos Pingüinos Rey hay en un zoológico. Para ello primero habría que saber distinguir a cuáles son este tipo de pingüinos y cuáles no. En un principio puede resultar fácil, y es que veremos que el distinguir elementos unos de otros puede llegar a complicarse cuando más consideraciones hacemos como el saber cuántos pingüinos hay que sean machos, o cuántos machos hay que no tengan más de un año, por ejemplo. Con este tipo de ejercicios los matemáticos fueron descubriendo con el tiempo que hacía falta poder estudiar un poco más a detalles este concepto de «diferenciar» y «contar» elementos de un conjunto. En las siguientes entradas vamos a desarrollar un poco más este concepto de diferenciar y contar.

Cardinalidad de un conjunto

Como todo en matemáticas, necesitaríamos hacer una definición de lo que significa que «un conjunto tenga $3$ elementos» y cómo es diferente a «un conjunto con $5$ elementos», por poner un ejemplo. Es con esto que damos la siguiente definición entre cardinalidad de un conjunto finito.

Definición. Sea $X$ un conjunto. Diremos que $X$ tiene cardinalidad finita o es finito si existe $n \in \mathbb{N}$ y una función biyectiva entre $X$ y $n$. En este caso escribiremos $|X|=n$.

Detengámonos un poco a analizar esta definición.

Recordemos que por ejemplo el número $2$ es escrito como conjunto como
$$ \{\emptyset,\{\emptyset\}\}$$.

Ahora pensemos en un conjunto con un plátano y una manazana. Entonces podemos definir la siguiente función $f: X \rightarrow \mathbb{N}$ como $f(manzana)= \emptyset$ y $f(plátano)=\{\emptyset\}$:

Puedes comprobar que esta función es biyectiva, y es solo una forma de biyectar el conjunto $X$ con el $2$. Dicho esto, entonces podemos decir que $|X|=2$. Ahora ¿Qué pasa con un conjunto que también tenga cardinalidad $2$? Digamos el conjunto $Y$ de un perro y un gato.

Entonces podríamos decir que igual puede haber una biyección entre los dos conjuntos $X$ y $Y$.

Ahora ¿Qué pasa si unimos los conjuntos de animales con los de ls frutas? Pues nuestra razón nos dirá que si en un conjunto tenemos dos elementos y en el otro dos, si los combinamos tendremos cuatro elementos, y esto es justamente otra de las bondades de la cardinalidad, pues se comporta de acuerdo a lo que nuestra razón nos dice.

Proposición Sean $X,Y$ dos conjuntos disjuntos. Si $|X|=n, |Y|=m$ entonces $|X \cup Y| = n+m$.

Demostración. Por definición de cardinalidad, existen dos funciones $g:X \rightarrow n$ y $f: Y \rightarrow m$ biyectivas. Notemos ahora que la función $h: X \cup Y \rightarrow n+m $ dada por $$h(x) = \begin{cases} &f(x), x \in X \\ g(x) + n, x \in Y \end{cases} $$ es biyectiva. Para demostrar que esta función es biyectiva, demostraremos la inyectividad y suprayectividad.

Es inyectiva. Considera dos elementos $x,y$ distintos. Existen tres casos, el primero es que $x,y \in X$, en este caso, $h(x)=f(x), h(y)=f(y)$ y como $f$ es inyectiva, sus imágenes son distintas.
El segundo caso es $x , y \in Y$. En este caso, recordemos que $h(x)=n+g(x)$ y $h(y) = n + g(y)$ Si las imágenes fueran iguales entonces $g(x)=g(y)$ pero esto solo sucede si $x=y$, pues $g$ es inyectiva, y esto contradiciendo la hipótesis de que los elementos son distintos.
Finalmente en el caso de que un elemento pertenezca a $X$, digamos $x$ y el otro a $Y$, digamos $y$, sucede que $h(x)=f(x)$, mientras que $h(y)=n+g(y)$, ahora notemos que $f: X \rightarrow n$, entonces ningún elemento es más grande que $n$, mientras que $h(y)$ sí es más grande que $n$, pues estamos uniendo números naturales al más grande número natural que compone al conjunto $X$, es decir, siempre sucederá que $h(x)<h(y)$ y en particular $h(x) \neq h(y)$, siendo la función inyectiva.

Además la función es suprayectiva, ya que para cualquier elemento $k \in n+m$ se tienen dos casos: Si $k <= n$ entonces existe $x \in X$ tal que $h(x)=f(x)=k$, mientras que si$k>n$ existe $l \in. \mathbb{N}$ tal que $n+l=k$. Por otro lado, como $g$ es suprayectiva, existe $y \in Y$ tal que $g(y)=l$. Así $h(y)=n+g(y)=n+l=k$. Por lo tanto la función es biyetiva.

Y más aún, hemos demostrado que los conjuntos disjuntos tienen cardinalidad $n+m$.

$\square$

El principio de las casillas

Una de las propiedades más importantes sobre cardinalidad que es intuitiva es la siguiente:

Proposición. (El principio de las casillas). Sean $X,Y$ dos conjuntos tales que $|X|=s(n)$ y $|Y|=n$. Entonces si $f:X \rightarrow Y$, $f$ no es inyectiva.

A esta se le llama principio de las casillas o de los palomares y se explica con el siguiente ejemplo:

Supón tienes $9$ casillas para palomas:

Naturalmente, solo cabrá a lo más una paloma en cada una de las casillas, entonces si lega al menos una paloma más, forzosamente tendría que haber más de una paloma en alguna de las casillas. En general para $n$ casillas, caben a lo más $n$ paloma para que quede solo una paloma en cada casilla. Es decir, podríamos hacer una inyección entre el número de palomas y el de casillas siempre y cuando haya menos palomas que casillas.

Demostración. Para ello deberíamos mostrar que no existe una inyección entre un conjunto de $n$ elementos y otro de $s(n)$.

Base de inducción. Sea $|X|=s(0)$ y $|Y|=0$. Notemos entonces que $Y$ tiene que ser el vacío, pues $0$ es el vacío y si $Y$ no fuera vacío, entonces existiría una función $f$ y un elemento $y \in Y$ tal que $f(y) \in \emptyset$. Lo cual es una contradicción. Ahora notemos que por vacuidad el enunciado se cumple, pues de no ser así, existiría una función $g:X \rightarrow Y$ inyectiva, pero esto supondría que $Im[g] \subset \emptyset$ tiene al menos un elemento.

Hipótesis de inducción. Ahora supongamos que para cualesquiera dos conjuntos $|X|=s(n)$ y $|Y|=n$ se cumple la condición.

Paso inductivo. Consideremos ahora dos conjuntos $X,Y$ con $|X|=s(s(n))$ y $|Y|=s(n)$. Ahora consideremos cualquier función $f: X \rightarrow Y$, bastará probar que esta función no es inyectiva. Para ello, notemos que si le quitamos cualquier elemento $x \in X$ a $X$, su cardinalidad será $s(n)$. Además si quitamos el elemento $y \in Y$ tal que $f(x)=y$ entonces $Y$ tiene cardinalidad $n$. Así volvemos al caso de la hipótesis de inducción donde la función $f’: X/\{x\} \rightarrow Y/{y}$ definida como $f'(x)=f(x)$ no es inyectiva, esto significa que existen dos elementos $y,z \in X/\{x\}$ tales que $f'(x)=f'(y)$. Más aún, la función $f$ tampoco es inyectiva por la existencia de estos dos elementos.

Así hemos demostrado el principio de las casillas.

$\square$

La cardinalidad de dos conjuntos

Una definición ahora sobre la cardinalidad de dos conjuntos es consecuencia de

Definición Dos conjuntos $X$ y $Y$ tienen la misma cardinalidad si existe una función biyectiva $f: X \rightarrow Y$ y lo escribiremos como $|X|=|Y|$

Y ahora veamos cómo es que en el caso finito, esta es una definición que no contradice la primera definición que dimos

Proposición En el caso finito, Son equivalentes para cualesquiera dos conjuntos finitos $X,Y$ y cualquier número natural $n$:

  1. $|X| = n \land |Y| = n$
  2. $|X| = |Y|$

Demostración.

$\Rightarrow$

Supongamos primero que $|X| = n$ y $|Y|=n$. Ahora, notemos que existen dos funciones biyectivas $f: X \rightarrow n$ y $g: Y \rightarrow n$ Ahora consideremos la siguiente función $g^{-1} \circ f : X \rightarrow Y$. Y notemos que es una biyección, pues como $g$ es biyectiva, en particular es suprayectiva y eso significa que $Im[g] = n$ Siendo entonces la función $g{-1}: Im[g] =n \rightarrow Y$ con el mismo dominio que el contradominio de $f$, es decir la composición es una función bien definida. Además como $f$ también es biyectiva, entonces $g^{-1} \circ f$ también es biyectiva.

$\Leftarrow$

Demostremos ahora por contradicción que $|X| = n \land |Y| = n$ cuando $|X|=|Y|$.

Para ello supongamos primero que existen dos naturales distintos $n,m$ tales que $|X|=n$ y $|Y|=m $, y esto es posible pues $X,Y$ son finitos. Y también $|X|=|Y|$ Ahora sin perdida de la generalidad supongamos que $n>m$. Pero esto es una contradicción al principio de las casillas, pues toda función de $X$ a $Y$ no sería inyectiva, y en general tampoco será biyectiva. Cumpliéndose así la condición deseada.

$\square$

Algunas propiedades más de la cardinalidad

Veamos ahora otras propiedades sobre las cardinalidades de los conjuntos. Para ello supón que $X$ es finito de cardinalidad $n$ y $Y$ es finito de cardinalidad $m$.

  • Proposición. $|X /Y| = |X| – |X \cap Y|$
    Demostración. Esto es consecuencia del hecho de que $X/Y$ y $X \cap Y$ son conjuntos disjuntos, entonces:
    $$ |X/Y| + |X \cap Y| = |X/Y \cup (X \cap Y)| = |X|$$

$\square$

  • Proposición. $|X \cup Y| = |X| + |Y| – |X \cap Y|$
    Demostración. Por el inciso anterior, sabemos que $$ |X \cup Y| = |X/Y \cup Y| = |X|- |X \cap Y| + |Y|$$

$\square$

  • Proposición. $|P({X)|=2^{|X|}$
    Demostración. Por inducción sobre el número de elementos en el conjunto $X$.
    Base de inducción. Si $X$ tiene $0$ elementos, entonces es el vacío, mientras que $P(X)={\emptyset}$ el cuál tiene cardinalidad $1=2^{0}$.
    Hipótesis de inducción. Ahora supongamos que si $|X|=n$ para algún número $n$ natural, entonces $|P(X)|=2^{n}$.
    Paso inductivo. Sea $|X|=n+1$. Consideremos ahora un elemento $x$ de $X$ y notemos que el conjunto $X/\{x\}$ es un conjunto con $n$ elementos, por lo cual sabemos que $|P(X/\{x\})|=2^n$. Ahora veamos que este conjunto describe todos los posibles subconjuntos de $X$ en los que $x$ no está incluído, por lo que si definimos el conjunto $P(X/\{x\}) \cup x := {A \cup x : A \in P(X/\{x\})}$, se tiene que $$(P(X/\{x\}) \cup x) \cup P(X/\{x\}) = P(X) $$ Pues el primer conjunto son todos los subconjuntos de $X$ que sí tienen a $x$ y el segundo aquellos que no. Como estos dos son conjuntos disjuntos y tienen exactamente $n$ elementos, entonces $$|P(X)| = |(P(X/\{x\}) \cup x) \cup P(X/\{x\})| = 2^n + 2^n = 2^{n+1}$$.

$\square$

Más adelante…

Ahora que hemos introducido el concepto de cardinalidad, veremos cómo es que podemos escalar este concepto del caso finito al caso infinito. Es decir ¿Qué pasa cuando ya no podemos hablar de conjuntos que podemos «contar»?

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra que $(P(X/\{x\}) \cup x) \cup P(X/\{x\}) = P(X)$
  2. Demuestra que $|X|=|Y|$ si y solo si $|Y|=|X|$
  3. Demuestra que la relación «tener la misma cardinalidad» es de equivalencia.
  4. ¿Cuál es la cardinalidad de |X \cup Y \cup Z|?

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

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

Por Fabian Ferrari

Deja un comentario

En esta entrada vemos algunos ejemplos más en donde se aplica el 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

\begin{align*}
s_1&=a_1\\
s_2&=a_1+a_2\\
s_3&=a_1+a_2+a_3\\
&\vdots\\
s_n&=a_1+a_2+ … +a_n.
\end{align*}

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\times 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\times 7$, dado que cualquier rectángulo que se pueda crear en un tablero de $3\times 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\times 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

Por Fabian Ferrari

Deja un comentario

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 $nk+1$ elementos en $n$ lugares, se tiene que uno de esos lugares tiene al menos $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. 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.