$S$ es el conjunto de todos los pares $(h,k)$ con $h,k$ enteros no negativos tales que $h+k<n$. Cada elemento de $S$ se colorea de rojo o azul, de forma que si $(h,k)$ es rojo y $h'\leqslant h$, $k'\leqslant k$, entonces $(h',k')$ también es rojo. Un subconjunto de $S$ de tipo $1$ tiene $n$ elementos azules con el primer miembro distinto y un subconjunto de $S$ de tipo $2$ tiene $n$ elementos azules con el segundo miembro distinto. Demostrar que hay la misma cantidad de subconjuntos de tipo $1$ que de tipo $2$.
Si $a_i$ es la cantidad de pares azules con el primer elemento igual a $i$ y $b_i$ es la cantidad de pares azules con el segundo elemento igual a $i$.
Queremos demostrar que $a_1\times a_2\times ...\times a_n=b_1\times b_2\times ...\times b_n$
Si encontramos una biyección entre los $a_i$ y los $b_j$ tal que $a_i=b_j$ estamos.
Ubicamos los puntos en un eje cartesiano y agregamos los puntos $(-1,k)$ con $0\leq k\leq n$ y $(h,-1)$ con $0\leq h \leq n$ y los pintamos de rojo y agregamos los puntos $(h,k)$ tales que $h+k=n$ y $h$ y $k$ son enteros no negativos y los pintamos de azul.
La cantidad de puntos azules en la columna $i$ es $a_i+1$ y la cantidad de puntos azules en la fila $j$ es $b_j+1$, si la columna $i$ y la fila $j$ tienen la misma cantidad de puntos azules entonces $a_i=b_j$
Si un punto azul tiene a la izquierda un punto rojo decimos que ese punto azul esta vivo y si un punto azul tiene abajo un punto rojo decimos que es punto azul esta muerto (un punto puede estar vivo y muerto al mismo tiempo).
Si el punto $(i,j)$ esta vivo entonces la fila $j$ tiene $n+1-j-i$ puntos azules, si el punto $(i,j)$ esta muerto entonces la columna $i$ tiene $n+1-i-j$ puntos azules.
Si el punto $(i,j)$ esta vivo y el punto $(a,b)$ esta muerto y $i+j=a+b$ entonces la fila $j$ y la columna $a$ tienen la misma cantidad de puntos azules por lo que si hago una biyección entre puntos vivos y puntos muertos de tal manera que si dos puntos están conectados entonces están en la misma diagonal de las que mantienen la suma constante terminaríamos el problema por lo que basta ver que en una diagonal hay la misma cantidad de puntos vivos que de muertos.
Miremos una de estas diagonales de suma constante $0\leq k<n-1$, tiene en sus extremos puntos rojos y cada segmento de puntos azules arranca con un punto vivo (ya que el anterior en la diagonal es rojo por lo que el de abajo de ese también es rojo y este esta a la izquierda del azul) y termina con uno muerto (ya que el siguiente en la diagonal es rojo por lo que el de la izquierda de ese también es rojo y este esta a abajo del azul). Ignorando estos puntos vivos de los comienzos y muertos de los finales de los segmentos, si un punto esta vivo a la izquierda tiene un rojo y este rojo arriba tiene un azul que esta muerto y si un punto esta muerto abajo tiene un rojo y este rojo a la derecha tiene un azul que esta vivo y ya tendríamos una biyección entre puntos vivos y muertos en la diagonal.
La diagonal de suma constante $n-1$ es igual que las anteriores solo que no tienen si o si extremos rojos pero si un extremo es azul este punto estará vivo o muerto depende de que extremo sea por lo que seria lo mismo que si agregáramos un punto rojo como extremo.
La diagonal de suma constante $n$ también es lo mismo solo que no contiene puntos rojos por lo que pasamos directamente a la parte en la que ignoramos los extremos de los segmentos.
Ejemplo $n=5$
IMG_20191222_010406.jpg
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.