1.3: Algunas aplicaciones de los principios básicos de conteo
- Page ID
- 112611
1.3.1: Caminos de celosía y números catalanes
\(\circ\) Exercise \(47\)
En una parte de una ciudad, todas las calles corren ya sea norte-sur o este-oeste, y no hay callejones sin salida. Supongamos que estamos parados en una esquina de calle. ¿De cuántas maneras podemos caminar a una esquina que está a cuatro cuadras al norte y seis cuadras al este, usando la menor cantidad de cuadras posible? (Pista).
\(\cdot\) Exercise \(48\)
El problema 47 tiene una interpretación geométrica en un plano de coordenadas. Una trayectoria de celosía en el plano es una “curva” compuesta por segmentos de línea que o bien van de un punto\((i, j)\) al punto\((i+1, j)\) o de un punto\((i, j)\) al punto\((i, j + 1)\), donde\(i\) y\(j\) son enteros. (Así los caminos de celosía siempre se mueven hacia arriba o hacia la derecha.) La longitud de la ruta es el número de dichos segmentos de línea.
\(\cdot\) Exercise \(49\)
Otro tipo de trayectoria geométrica en el plano es una trayectoria de celosía diagonal. Tal ruta es una ruta compuesta por segmentos de línea que van de un punto\((i, j)\) a\((i+1, j+1)\) (esto a menudo se llama un upstep) o\((i+1, j-1)\) (esto a menudo se llama un downstep), nuevamente donde i y j son enteros. (Así, los caminos diagonales de celosía siempre se mueven hacia la derecha pero pueden moverse hacia arriba o hacia abajo).
- Describa a qué puntos están conectados\((0, 0)\) por caminos de celosía diagonales. (Pista).
- ¿Cuál es la longitud de una trayectoria de celosía diagonal desde\((0, 0)\) hasta\((m, n)\)?
- Suponiendo que ese\((m, n)\) es un punto desde el que se puede llegar\((0, 0)\), ¿cuántos caminos diagonales de celosía hay de\((0, 0)\) a\((m, n)\)? (Pista).
\(\circ\) Exercise \(50\)
Una obra escolar requiere una donación de diez dólares por persona; la donación va al fondo de actividades estudiantiles. Supongamos que cada persona que viene a la obra paga con un billete de diez dólares o un billete de veinte dólares. El maestro que está recogiendo el dinero se olvidó de conseguir el cambio antes del evento. Si siempre hay al menos tantas personas que han pagado con diez como veinte como llegan el maestro no tendrá que darle a nadie un pagaré por cambio. Supongamos que la\(2n\) gente viene a la obra, y exactamente la mitad de ellos paga con billetes de diez dólares.
- Describir una biyección entre el conjunto de secuencias de decenas y veinte que la gente da al maestro y el conjunto de caminos de celosía de\((0, 0)\) a\((n, n)\).
- Describir una biyección entre el conjunto de secuencias de decenas y veinte que la gente le da al maestro y el conjunto de caminos de celosía diagonales entre\((0, 0)\) y\((2n, 0)\).
- En cada una de las partes anteriores, ¿cuál es la interpretación geométrica de una secuencia que no requiere que el maestro dé ningún pagaré? (Pista).
\(→ \; \cdot\) Exercise \(51\)
Observe que una trayectoria de celosía de\((0, 0)\) a\((n, n)\) permanece dentro (o en los bordes de) el cuadrado cuyos lados son el\(x\) eje -eje, el\(y\) -eje, la línea\(x = n\) y la línea\(y = n\). En este problema vamos a calcular el número de caminos de celosía desde\((0,0)\) hasta\((n, n)\) que permanecen dentro (o en los bordes de) el triángulo cuyos lados son el\(x\) eje -eje, la línea\(x = n\) y la línea\(y = x\). Tales caminos de celosía se llaman caminos catalanes. Por ejemplo, en la Figura 1.3.1 mostramos la cuadrícula de puntos con coordenadas enteras para el triángulo cuyos lados son el\(x\) eje -eje, la línea\(x = 4\) y la línea\(y = x\).
a. Explique por qué el número de trayectorias de celosía desde\((0, 0)\) hasta\((n, n)\) que salen del triángulo descrito anteriormente es el número de trayectorias de celosía desde\((0, 0)\) hasta\((n, n)\) que tocan o cruzan la línea\(y = x + 1\).
b. encontrar una bijección entre caminos de celosía de\((0, 0)\) a\((n, n)\) ese toque (o cruce) la línea\(y = x+1\) y caminos de celosía de\((−1, 1)\) a\((n, n)\). (Pista).
c. Encontrar una fórmula para el número de caminos de celosía desde\((0, 0)\) hasta\((n, n)\) que no van por encima de la línea\(y = x\). El número de tales rutas se llama Número Catalán y generalmente se denota por\(C_{n}\). (Pista).
\(\rightarrow\) Exercise \(52\)
Su fórmula para el Número Catalán se puede expresar como un coeficiente binomial dividido por un entero. Siempre que tenemos una fórmula que requiere la división por un entero, una explicación combinatoria ideal de la fórmula es aquella que usa el principio del cociente. El propósito de este problema es encontrar tal explicación utilizando caminos de celosía diagonales. Un camino de celosía diagonal que nunca va por debajo de la\(y\) coordenada -de su primer punto se llama Dyck Path. Llamaremos a un Sendero Dyck de\((0, 0)\) a\((2n, 0)\) un Sendero Catalán (diagonal) de longitud\(2n\). Así el número de Caminos Catalanes (diagonales) de longitud\(2n\) es el Número Catalán\(C_n\). Normalmente podemos decidir desde el contexto si la frase Trayectoria Catalana se refiere a un camino diagonal, por lo que normalmente dejamos fuera la palabra diagonal.
- Si un Dyck Path tiene\(n\) pasos (cada uno un paso ascendente o descendente), ¿por qué los primeros\(k\) pasos forman un Dyck Path para cada no negativo\(k \leq n\)?
- Pensada como una curva en el plano, una trayectoria de celosía diagonal puede tener muchos máximos y mínimos locales, y puede tener varios máximos y mínimos absolutos, es decir, varios puntos más altos y varios puntos más bajos. ¿Cuál es la\(y\) coordenada de un punto mínimo absoluto de un Dyck Path a partir de\((0, 0)\)? Explique por qué un Dyck Path cuyo punto mínimo absoluto más a la derecha es su último punto es un Sendero Catalán. (Pista).
- Dejar\(D\) ser el conjunto de todas las trayectorias de celosía diagonales de\((0, 0)\) a\((2n, 0)\). (Por lo tanto, estos caminos pueden ir por debajo del\(x\) eje.) Supongamos que\(D\) particionamos dejando\(B_{i}\) ser el conjunto de trayectorias de celosía en las\(D\) que tienen\(i\) upsteps (quizás mezclados con algunos downsteps) siguiendo el último mínimo absoluto. ¿Cuántos bloques tiene esta partición? Dar una descripción sucinta del bloque\(B_{0}\). (Pista).
- ¿Cuántos repuntes hay en un Camino Catalán?
- *Vamos a dar una bijección entre el conjunto de Caminos Catalanes y el bloque\(B_{i}\) para cada uno\(i\) entre\(1\) y\(n\). Por ahora, supongamos que el valor de\(i\), aunque desconocido, es fijo. Tomamos un camino catalán y lo rompemos en tres pedazos. La pieza\(F\) (para “front”) consiste en todos los escalones antes del\(i^{\text{th}}\) upstep en el camino catalán. La pieza\(U\) (para “arriba”) consiste en el\(i^{\text{th}}\) upstep. La pieza\(B\) (para “atrás”) es la porción del camino que sigue el\(i^{\text{th}}\) escalón. Así podemos pensar en el camino como\(F U B\). Mostrar que la función que lleva\(F U B\) a\(B U F\) es una bijección del conjunto de Caminos Catalanes al bloque\(B_{i}\) de la partición. (Observe que\(B U F\) puede ir por debajo del\(x\) eje.) (Pista).
- Explica cómo acabas de dar otra prueba de la fórmula para los Números Catalanes.
1.3.2: El Teorema Binomial
\(\circ\) Exercise \(53\)
Eso lo sabemos\((x+y)^{2} = x^{2}+2xy+y^{2}\). Multiplique ambos lados por\((x+y)\) para obtener una fórmula para\((x + y)^{3}\) y repita para obtener una fórmula para\((x + y)^{4}\). ¿Ves un patrón? Si es así, ¿qué es? Si no es así, repita el proceso para obtener una fórmula\((x + y)^{5}\) y mira hacia atrás en la Figura 1.2.4 para ver el patrón. Conjetura una fórmula para\((x + y)^{n}\).
\(\bullet\) Exercise \(54\)
Cuando aplicamos los\(n\) tiempos de ley distributiva a\((x+y)^{n}\), obtenemos una suma de términos de la forma\(x^{i}y^{n−i}\) para diversos valores del entero\(i\).
- Si te queda claro que cada término de la forma\(x^{i}y^{n−i}\) que obtenemos proviene de elegir un\(x\)\(i\) de los\((x + y)\) factores y\(y\) a del resto\(n - i\) de los factores y multiplicar estas elecciones juntas, entonces responde esta parte del problema y salta la siguiente parte. De lo contrario, haz la siguiente parte en lugar de esta. ¿De cuántas maneras podemos elegir\(x\) entre\(i\) términos y\(y\) entre\(n - i\) términos?
- Ampliar el producto\((x_{1} + y_{1})(x_{2} + y_{2})(x_{3} + y_{3})\).
- ¿Qué obtienes cuando\(x\) sustituyes a cada uno\(x_{i}\) y\(y\) por cada uno\(y_{i}\)?
- Ahora imagina expandirte
\[(x_{1} + y_{1})(x_{2} + y_{2}) \dotsi (x_{n} + y_{n}).\]
Una vez que aplicas la ley conmutativa a los términos individuales que obtengas, tendrás una suma de términos de la forma
\[x_{k_{1}}x_{k_{2}} \dotsi x_{k_{i}} \cdot y_{j_{1}}y_{j_{2}} \dotsi y_{j_{n−i}}.\]
¿Cuál es el conjunto\(\{k_{1}, k_{2}, \dotsc, k_{i}\} \bigcup \{j_{1}, j_{2}, \dotsc, j_{n−i}\}\)? - ¿De cuántas maneras puedes elegir el conjunto\(\{k_{1}, k_{2}, \dotsc, k_{i}\}\)?
- Una vez que hayas elegido este conjunto, ¿para cuántas opciones tienes\(\{j_{1}, j_{2}, \dotsc, j_{n−i}\}\)?
- Si sustituye\(x\) a cada uno\(x_i\) y\(y\) por cada uno\(y_i\), cuántos términos del formulario\(x^iy^{n−i}\) tendrá en el producto ampliado
\[(x_{1} + y_{1})(x_{2} + y_{2}) \dotsc (x_{n} + y_{n}) = (x + y)^{n}?\] - ¿Cuántos términos del formulario\(x^{n−i}y^{i}\) vas a tener?
- Explica cómo acabas de probar tu conjetura desde Problema. El teorema que has probado se llama Teorema Binomial.
Ejercicio\(55\)
¿Qué es\(\Sigma^{10}_{i=1}\binom{10}{i}3^{i}\)? (Pista).
Ejercicio\(56\)
¿Qué\(n\) es\(\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dotsi \pm \binom{n}{n}\) si un entero es mayor que cero? (Pista).
\(\rightarrow \bullet\) Exercise \(57\)
Explicar por qué
\(\sum^{k}_{i=0} \binom{m}{i} \binom{n}{k-i} = \binom{m+n}{k}\)
Encuentra dos explicaciones diferentes. (Pista).
\(\rightarrow\) Exercise \(58\)
A partir de la simetría de los coeficientes binomiales, no es demasiado difícil ver que cuando\(n\) es un número impar, el número de subconjuntos\(\{1, 2, . . . , n\}\) de tamaño impar es igual al número de subconjuntos\(\{1, 2, . . . , n\}\) de tamaño par. ¿Es cierto que cuando\(n\) es par el número de subconjuntos de\(\{1, 2, . . . , n\}\) de tamaño par es igual al número de subconjuntos de tamaño impar? ¿Por qué o por qué no? (Pista).
\(\rightarrow\) Exercise \(59\)
¿Qué es\(\Sigma^{n}_{i=0} i \binom{n}{i}\)? (Pista: piensa en cómo podrías usar el cálculo.) (Pista).
Observe cómo la prueba que dio del teorema binomial fue un argumento de conteo. Es interesante que un teorema aparentemente algebraico que nos dice cómo expandir un poder de un binomio sea probado por un argumento que equivale a contar los términos individuales de la expansión. Parte de la razón por la que las matemáticas combinatorias resultan tan útiles es que los argumentos de conteo a menudo subyacen a resultados importantes del álgebra. A medida que el álgebra se vuelve más sofisticado, también lo hacen las familias de objetos que tenemos que contar, pero no obstante podemos desarrollar una gran cantidad de álgebra sobre la base del conteo.
1.3.3: El principio del encasillamiento
\(\circ\) Exercise \(\PageIndex{1}\)
Las monedas americanas están todas marcadas con el año en que se fabricaron. ¿Cuántas monedas necesitas tener en tu mano para garantizar que en dos (al menos) de ellas, la fecha tenga el mismo último dígito? (Cuando decimos “para garantizar eso en dos (al menos) de ellos,...” queremos decir que puedes encontrar dos con el mismo último dígito. Es posible que puedas encontrar tres con ese último dígito, o podrías encontrar un par con el último dígito\(1\) y un par con el último dígito\(9\), o cualquier combinación de últimos dígitos iguales, siempre y cuando haya al menos un par con el mismo último dígito).
Hay muchas maneras en las que podrías explicar tu respuesta al Problema 60. Por ejemplo, puedes dividir las monedas según el último dígito de su fecha; es decir, juntas todas las monedas con un último dígito dado en un bloque, y no pones otras monedas en ese bloque; repitiendo hasta que todas las monedas estén en algún bloque. Entonces tienes una partición de tu juego de monedas. Si no hay dos monedas que tengan el mismo último dígito, entonces cada bloque tiene exactamente una moneda. Dado que solo hay diez dígitos, hay como máximo diez bloques y así por el principio de suma hay como máximo diez monedas. De hecho, con diez monedas es posible no tener dos con el mismo último dígito, pero con\(11\) monedas algún bloque debe tener al menos dos monedas para que sea la suma de los tamaños de como máximo diez bloques\(11\). Esta es una explicación de por qué necesitamos\(11\) monedas en el Problema 60. Este tipo de situación surge a menudo en situaciones combinatorias, por lo que en lugar de usar siempre el principio de suma para explicar nuestro razonamiento, enunciamos otro principio que podemos pensar como otra variante más del principio de suma. El principio del encasillamiento establece que
Si particionamos un conjunto con más de\(n\) elementos en\(n\) partes, entonces al menos una parte tiene más de un elemento.
El principio del casillero recibe su nombre de la idea de una cuadrícula de cajitas que podrían usarse, por ejemplo, para ordenar el correo, o como buzones de correo para un grupo de personas en una oficina. Las cajas en tales rejillas a veces se llaman palomeros en analogía con pilas de cajas utilizadas para albergar palomas mensajeras cuando las palomas mensajeras se usaban para llevar mensajes. La gente a veces va a declarar el principio de una manera más colorida como “si metemos más que\(n\)\(n\) palomas en los casilleros, entonces algún palomar tiene más de una paloma”.
Ejercicio\(61\)
Mostrar que si tenemos una función de un conjunto de tamaño\(n\) a un conjunto de tamaño menor que\(n\), entonces no\(f\) es uno a uno. (Pista).
\(\bullet\) Exercise \(62\)
Mostrar que si\(S\) y\(T\) son conjuntos finitos del mismo tamaño, entonces una función\(f\) de\(S\) a\(T\) es uno a uno si y solo si está en. (Pista).
\(\cdot\) Exercise \(63\)
Existe un principio generalizado de encasillamiento que dice que si partimos un conjunto con más de\(kn\) elementos en\(n\) bloques, entonces al menos un bloque tiene al menos\(k + 1\) elementos. Demostrar el principio de encasillamiento generalizado. (Pista).
Ejercicio\(64\)
Todos los poderes de cinco terminan en un cinco, y todos los poderes de dos son parejos. Demuestra que para algún entero\(n\), si tomas los primeros\(n\) poderes de un primo distinto de dos o cinco, uno debe tener “\(01\)” como los dos últimos dígitos. (Pista).
\(\rightarrow \; \cdot\) Exercise \(65\)
Demostrar que en un conjunto de seis personas, hay un conjunto de al menos tres personas que todas se conocen, o un conjunto de al menos tres personas ninguna de las cuales se conoce. (Suponemos que si la persona 1 conoce a la persona 2, entonces la persona 2 conoce a la persona 1.) (Pista).
\(\cdot\) Exercise \(66\)
Dibuja cinco círculos etiquetados como Al, Sue, Don, Pam y Jo. Encuentra la manera de trazar líneas rojas y verdes entre las personas para que cada par de personas esté unido por una línea y no haya ni un triángulo que consista enteramente en líneas rojas ni un triángulo compuesto por líneas verdes. ¿Qué te dice el Problema 65 sobre la posibilidad de hacer esto con los nombres de seis personas? ¿Qué dice este problema sobre la conclusión de la celebración del Problema 65 cuando hay cinco personas en nuestro set en lugar de seis?
1.3.4: Números Ramsey
Los problemas 65 y 66 en conjunto muestran que seis es el número más pequeño\(R\) con la propiedad que si tenemos\(R\) gente en una habitación, entonces hay o un conjunto de (al menos) tres conocidos mutuos o un conjunto de (al menos) tres desconocidos mutuos. Otra forma de decir lo mismo es decir que seis es el número más pequeño para que no importa cómo conectemos seis puntos en el plano (no hay tres en una línea) con líneas rojas y verdes, podemos encontrar ya sea un triángulo rojo o un triángulo verde. Hay un nombre para esta propiedad. El Número Ramsey\(R(m, n)\) es el número más pequeño\(R\) para que si tenemos\(R\) gente en una habitación, entonces hay un conjunto de al menos m conocidos mutuos o al menos extraños\(n\) mutuos. También hay una descripción geométrica de Ramsey Numbers; utiliza la idea de una gráfica completa sobre\(R\) vértices. Una gráfica completa sobre\(R\) vértices consiste en\(R\) puntos en el plano, junto con segmentos de línea (o curvas) que conectan cada uno de los dos\(R\) vértices. 1 Los puntos se denominan vértices y los segmentos de línea se denominan bordes. En la Figura 1.3.2 mostramos tres formas diferentes de dibujar una gráfica completa en cuatro vértices. Solemos\(K_{n}\) representar una gráfica completa en\(n\) vértices.
Nuestra descripción geométrica de\(R(3, 3)\) puede traducirse al lenguaje de la teoría gráfica (que es el tema que incluye gráficas completas) diciendo que\(R(3, 3)\) es el número más pequeño\(R\) para que si coloreamos los bordes de una\(K_{R}\) con dos colores, entonces podamos encontrar en nuestra imagen un\(K_{3}\) todos cuyos bordes tienen el mismo color. La descripción de la teoría gráfica de\(R(m, n)\)\(R(m, n)\) es que es el número más pequeño de\(R\) manera que si coloreamos los bordes de a\(K_{R}\) con rojo y verde, entonces podemos encontrar en nuestra imagen ya sea un Km todos cuyos bordes son rojos o un\(K_{n}\) todos cuyos bordes son verdes. Debido a que podríamos haber dicho nuestros colores en el orden opuesto, podemos concluir eso\(R(m, n) = R(n,m)\). En particular,\(R(n, n)\) es el número más pequeño\(R\) tal que si coloreamos los bordes de una\(K_{R}\) con dos colores, entonces nuestra imagen contiene un Kn todos cuyos bordes tienen el mismo color.
\(\cdot\) Exercise \(67\)
Ya que\(R(3, 3) = 6\), una suposición sin educación podría ser esa\(R(4, 4) = 8\). Demuestre que este no es el caso. (Pista).
\(\cdot\) Exercise \(68\)
Demostrar que entre diez personas, hay o cuatro conocidos mutuos o tres desconocidos mutuos. ¿De qué dice esto\(R(4, 3)\)? (Pista).
\(\cdot\) Exercise \(69\)
Demostrar que entre un número impar de personas hay al menos una persona que es un conocido de un número par de personas y por lo tanto también un extraño para un número par de personas. (Pista).
\(\cdot\) Exercise \(70\)
Encuentra una manera de colorear los bordes de un\(K_{8}\) con rojo y verde para que no haya rojo\(K_{4}\) ni verde\(K_{3}\). (Pista).
\(\rightarrow \; \cdot\) Exercise \(71\)
Encontrar\(R(4, 3)\). (Pista).
Al momento de escribir esto, se conocen relativamente pocos Números Ramsey. \(R(3, n)\)es conocido por\(n < 10, R(4, 4) = 18\), y\(R(5, 4) = R(4, 5) = 25\).