Entre mis opciones nacionales para la maestría tengo el Posgrado Conjunto en Ciencias Matemáticas por aquella cuestión de la Física Matemática (y e.g. que el buenazo de Alejandro Corichi anda por allá, aunque trabaje en LQG, que no necesariamente es de mi interés). El examen de admisión es obligatorio, y como físico es de esperar que encuentre cierta adversidad con algunas cuestiones. De cualquier modo la situación no es grave y sólo se trata de ponerse al corriente (acá se pueden consultar exámenes de admisión anteriores). Muestro dos situaciones que me resultaron bastante entretenidas y que un físico rara vez se encuentra o con las que lidia muy poco durante la licenciatura. Los problemas son del examen de noviembre de 2012.
----------
1. ¿Cuántas funciones suprayectivas hay de un conjunto con 5 elementos en otro con 3?
El total de funciones (supra y no-supra) es $3^5$: el argumento es básicamente el de todas las salidas posibles de un 'dado' con 3 caras tirado 5 veces. De este total entonces hay que quitar las que no son supra.
Supóngase que el codominio es un conjunto $C=\{a,b,c\}$. Entonces todas las funciones que no son supra son aquellas que no toman o uno o dos elementos de $C$: de las que dejan un elemento se tienen $3\cdot2^5$ funciones (i.e. $2^5$ por cada elemento ignorado) mientras que las que dejan dos elementos son simplemente $3\cdot1^5=3$.
De aquí se podría pensar que $3^5-3\cdot2^5-3$ es el total de funciones supra, de cualquier modo no es así. Véase que este argumento funciona si se reemplaza 5 por cualquier $n\geq3$, entonces si se quisiera investigar el total de funciones supra de un conjunto de 3 elementos en otro de 3, se tendría $3^3-3\cdot2^3-3=0$, lo que evidentemente es incorrecto. El problema es que al ignorar o uno o dos elementos de $C$, se están considerando (i.e. se están restando) más veces las funciones que mandan de un elemento del dominio a otro de $C$ no ignorado, e.g. si consideramos todas las funciones que mandan de un elemento del dominio a $a\in{C}$ al ignorar otro(s), estamos considerando estas funciones 3 veces: una al ignorar $b$, otra al ignorar $c$ y otra al ignorar ambos. Entonces se tiene que tomar en cuenta esto no sólo para todas las que mandan a $a$ ignorando otra(s) si no también las que mandan a $b$ y $c$; i.e. pues, que si originalmente se restaban $3\cdot2^5-3$ funciones, se tienen que complementar las $2\cdot3$ funciones que estabamos descartando de más, de modo que sólo se consideren una vez (de ahí el 2 por cada elemento de $C$).
Así entonces, se tienen
\begin{equation}3^5-3\cdot2^5-3+2\cdot3=3(3^4-2^5+1)=150\end{equation} funciones supra de un conjunto con 5 elementos en otro con 3.
Éste es el argumento de a pie. Naturalmente uno se pregunta en general cuál es el total de funciones supra de un conjunto de $n$ elementos en un conjunto de $m$ elementos. Luego de un buen cursito de combinatoria uno contestará
\begin{equation}m!\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{j=0}^m(-1)^j\binom{m}{j}(m-j)^n\end{equation} donde $\left\{\begin{matrix}n\\m\end{matrix}\right\}$ son los números de Stirling de segunda especie. Por definición, estos números son la cantidad de maneras que existen de hacer una partición de un conjunto de $n$ elementos en $m$ subconjuntos y el factor $m!$ extra viene de que en este problema cada elemento del codominio se asocia con cualquiera de estos subconjuntos. Hasta poco antes de escribir esta entrada, desconocía estos números, pero al menos ahora sé que existen y procuraré investigar más acerca de estos, que presuntamente tienen varias propiedades y usos interesantes.
----------
2. Sea $z=a_1a_2\cdots{a}_s\in\mathbb{Z}$, donde $a_i$ es el $i$-ésimo dígito.
Pruebe que $z$ es divisible entre 11 si y sólo si 11 divide a \begin{equation}\sum_{i\,\text{par}}a_i-\sum_{i\,\text{impar}}a_i\end{equation} (hint: encuentre el residuo de $10^k$ al dividir entre 11)
Se tiene que
\begin{align}
10^0&=11(0)+1\nonumber\\
10^1&=11(1)-1\nonumber\\
10^2&=11(9)+1\nonumber\\
10^3&=11(91)-1\nonumber\\
10^4&=11(909)+1\nonumber\\
\vdots&\nonumber\\
10^k&=\begin{cases}11a+1,&\text{si}\,k\,\text{par}\\11b-1,&\text{si}\,k\,\text{impar}\end{cases}\label{1}
\end{align} y $z$ puede escribirse como
\begin{equation}z=10^{s-1}a_1+10^{s-2}a_2+\ldots+10a_{s-1}+a_s\end{equation} de modo entonces que si $11|z$, $\exists{c}\in\mathbb{Z}$ tal que
\begin{equation}z=10^{s-1}a_1+10^{s-2}a_2+\ldots+10a_{s-1}+a_s=11c\end{equation} es decir, a partir de las ec. (\ref{1})
\begin{equation}\sum_{i\,\text{par}}a_i-\sum_{i\,\text{impar}}a_i+11d=11c\end{equation} con $d$ la suma de todos los términos multiplicados por $11$, salvo un signo, que puede absorberse simplemente en $c$. De aquí se sigue que $z=11c$ siempre que también exista algún $\ell\in\mathbb{Z}$ tal que $\sum_{i\,\text{par}}a_i-\sum_{i\,\text{impar}}a_i=11\ell$.
Este problema me parece mucho más sencillo que el anterior, sin embargo también me parece sumamente interesante, como toda la Teoría de Números (este mismo blog es testigo). Así como el caso del 11, existen reglas de divisibilidad para otros enteros que son impresionantes y uno se la puede pasar bomba mostrándolas: acá se muestran algunas.
----------
El total de funciones (supra y no-supra) es $3^5$: el argumento es básicamente el de todas las salidas posibles de un 'dado' con 3 caras tirado 5 veces. De este total entonces hay que quitar las que no son supra.
Supóngase que el codominio es un conjunto $C=\{a,b,c\}$. Entonces todas las funciones que no son supra son aquellas que no toman o uno o dos elementos de $C$: de las que dejan un elemento se tienen $3\cdot2^5$ funciones (i.e. $2^5$ por cada elemento ignorado) mientras que las que dejan dos elementos son simplemente $3\cdot1^5=3$.
De aquí se podría pensar que $3^5-3\cdot2^5-3$ es el total de funciones supra, de cualquier modo no es así. Véase que este argumento funciona si se reemplaza 5 por cualquier $n\geq3$, entonces si se quisiera investigar el total de funciones supra de un conjunto de 3 elementos en otro de 3, se tendría $3^3-3\cdot2^3-3=0$, lo que evidentemente es incorrecto. El problema es que al ignorar o uno o dos elementos de $C$, se están considerando (i.e. se están restando) más veces las funciones que mandan de un elemento del dominio a otro de $C$ no ignorado, e.g. si consideramos todas las funciones que mandan de un elemento del dominio a $a\in{C}$ al ignorar otro(s), estamos considerando estas funciones 3 veces: una al ignorar $b$, otra al ignorar $c$ y otra al ignorar ambos. Entonces se tiene que tomar en cuenta esto no sólo para todas las que mandan a $a$ ignorando otra(s) si no también las que mandan a $b$ y $c$; i.e. pues, que si originalmente se restaban $3\cdot2^5-3$ funciones, se tienen que complementar las $2\cdot3$ funciones que estabamos descartando de más, de modo que sólo se consideren una vez (de ahí el 2 por cada elemento de $C$).
Así entonces, se tienen
\begin{equation}3^5-3\cdot2^5-3+2\cdot3=3(3^4-2^5+1)=150\end{equation} funciones supra de un conjunto con 5 elementos en otro con 3.
Éste es el argumento de a pie. Naturalmente uno se pregunta en general cuál es el total de funciones supra de un conjunto de $n$ elementos en un conjunto de $m$ elementos. Luego de un buen cursito de combinatoria uno contestará
\begin{equation}m!\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{j=0}^m(-1)^j\binom{m}{j}(m-j)^n\end{equation} donde $\left\{\begin{matrix}n\\m\end{matrix}\right\}$ son los números de Stirling de segunda especie. Por definición, estos números son la cantidad de maneras que existen de hacer una partición de un conjunto de $n$ elementos en $m$ subconjuntos y el factor $m!$ extra viene de que en este problema cada elemento del codominio se asocia con cualquiera de estos subconjuntos. Hasta poco antes de escribir esta entrada, desconocía estos números, pero al menos ahora sé que existen y procuraré investigar más acerca de estos, que presuntamente tienen varias propiedades y usos interesantes.
----------
Pruebe que $z$ es divisible entre 11 si y sólo si 11 divide a \begin{equation}\sum_{i\,\text{par}}a_i-\sum_{i\,\text{impar}}a_i\end{equation} (hint: encuentre el residuo de $10^k$ al dividir entre 11)
Se tiene que
\begin{align}
10^0&=11(0)+1\nonumber\\
10^1&=11(1)-1\nonumber\\
10^2&=11(9)+1\nonumber\\
10^3&=11(91)-1\nonumber\\
10^4&=11(909)+1\nonumber\\
\vdots&\nonumber\\
10^k&=\begin{cases}11a+1,&\text{si}\,k\,\text{par}\\11b-1,&\text{si}\,k\,\text{impar}\end{cases}\label{1}
\end{align} y $z$ puede escribirse como
\begin{equation}z=10^{s-1}a_1+10^{s-2}a_2+\ldots+10a_{s-1}+a_s\end{equation} de modo entonces que si $11|z$, $\exists{c}\in\mathbb{Z}$ tal que
\begin{equation}z=10^{s-1}a_1+10^{s-2}a_2+\ldots+10a_{s-1}+a_s=11c\end{equation} es decir, a partir de las ec. (\ref{1})
\begin{equation}\sum_{i\,\text{par}}a_i-\sum_{i\,\text{impar}}a_i+11d=11c\end{equation} con $d$ la suma de todos los términos multiplicados por $11$, salvo un signo, que puede absorberse simplemente en $c$. De aquí se sigue que $z=11c$ siempre que también exista algún $\ell\in\mathbb{Z}$ tal que $\sum_{i\,\text{par}}a_i-\sum_{i\,\text{impar}}a_i=11\ell$.
Este problema me parece mucho más sencillo que el anterior, sin embargo también me parece sumamente interesante, como toda la Teoría de Números (este mismo blog es testigo). Así como el caso del 11, existen reglas de divisibilidad para otros enteros que son impresionantes y uno se la puede pasar bomba mostrándolas: acá se muestran algunas.
No comments:
Post a Comment