Cada bacteria tiene un cuerpo horizontal con longitud natural y algún número no negativo de pies verticales, cada uno con longitud natural no negativa (!), que se encuentran debajo de su cuerpo. ¿De cuántas maneras pueden estas bacterias llenar una tabla de $m\times n$ de tal manera que ninguna de ellas se superponga?

Suponga que $n$ es un número natural. Llamamos a la secuencia $(x_1,y_1,z_1,t_1),(x_2,y_2,z_2,t_2),.....,(x_s,y_s,z_s,t_s)$ de $\mathbb Z^4$ buena si satisface estas tres condiciones: i) $x_1=y_1=z_1=t_1=0$ . ii) las secuencias $x_i,y_i,z_i,t_i$ son estrictamente crecientes. iii) $x_s+y_s+z_s+t_s=n$ . (note que $s$ puede variar). Encuentre el número de secuencias buenas.

Decimos que el punto $i$ en la permutación $\sigma$ está en curso si para cada $j<i$ tenemos $\sigma (j)<\sigma (i)$ . a) pruebe que el número de permutaciones del conjunto $\{1,....,n\}$ con exactamente $r$ puntos en curso es $s(n,r)$ . b) pruebe que el número de palabras de $n$ letras con letras $\{a_1,....,a_k\},a_1<.....<a_k$ con exactamente $r$ puntos en curso es $\sum_{m}\binom{k}{m} S(n,m) s(m,r)$ .

Suponga que $p(n)$ es el número de particiones de un número natural $n$ . Pruebe que existe $c>0$ tal que $P(n)\ge n^{c \cdot \log n}$ .

Pruebe que el número de permutaciones tales que el orden de cada elemento es un múltiplo de $d$ es $\frac{n!}{(\frac{n}{d})!d^{\frac{n}{d}}} \prod_{i=0}^{\frac{n}{d}-1} (id+1)$ .

Pruebe que si el grafo $G$ es un árbol, entonces existe un vértice que es común entre todos los caminos más largos.

Pruebe que estas tres afirmaciones son equivalentes: (a) Para cada función continua $f:S^n \to \mathbb R^n$ , existe un $x\in S^n$ tal que $f(x)=f(-x)$ . (b) No existe una aplicación antípoda $f:S^n \to S^{n-1}$ . (c) Para cada cobertura de $S^n$ con conjuntos cerrados $A_0,\dots,A_n$ , existe un índice $i$ tal que $A_i\cap -A_i\neq \emptyset$ .

Con la ayuda de la parte (b), demuestre que el siguiente teorema es verdadero: Dos ladrones quieren dividir un collar abierto que tiene $d$ diferentes tipos de piedras, donde el número de piedras de cada tipo es par, de tal manera que cada uno de los ladrones recibe el mismo número de piedras de cada tipo. Demuestre que los dos ladrones pueden lograr esto cortando el collar en a lo sumo $d$ lugares.

Con la ayuda de la parte (b), demuestre que el siguiente teorema es verdadero: Dos ladrones quieren dividir un collar abierto que tiene $d$ diferentes tipos de piedras, donde el número de piedras de cada tipo es par, de tal manera que cada uno de los ladrones recibe el mismo número de piedras de cada tipo. Demuestre que los dos ladrones pueden lograr esto cortando el collar en a lo sumo $d$ lugares.

Decimos que un hiperplano $H$ dado por la ecuación \[H=\{(x_1,\dots,x_n)\in \mathbb R^n \mid a_1x_1+ \dots +a_nx_n=b\}\] ($a=(a_1,\dots,a_n)\in \mathbb R^n$ y $b\in \mathbb R$ constante) biseca el conjunto finito $A\subseteq \mathbb R^n$ si cada uno de los dos semi-espacios $H^+=\{(x_1,\dots,x_n)\in \mathbb R^n \mid a_1x_1+ \dots +a_nx_n>b\}$ y $H^-=\{(x_1,\dots,x_n)\in \mathbb R^n \mid a_1x_1+ \dots +a_nx_n<b\}$ tiene a lo sumo $\lfloor \tfrac{|A|}{2}\rfloor$ puntos de $A$ . Suponga que $A_1,\dots,A_n$ son subconjuntos finitos de $\mathbb R^n$ . Pruebe que existe un hiperplano $H$ en $\mathbb R^n$ que biseca todos ellos al mismo tiempo.