Para $k<n/2$ construir una biyección $f$ de $k$ -subconjuntos de $[n]$ a $(n-k)$ -subconjuntos s.t. $x\subseteq f(x)$

Question

Para $k$ menos de $n/2$ construye una biyección desde el $k$ -subconjuntos de $n$ a la $(n-k)$ -subsets, tal que $x$ es un subconjunto de $f(x)$ .

Este es un problema de un conjunto de problemas de 2004 de Google, y las respuestas se han publicado, pero no pudo encontrar una buena respuesta para este.

Answer 1

Creo que se puede dar una construcción explícita como la siguiente:

Nótese que todo lo que tenemos que hacer es encontrar una biyección $\displaystyle F$ de $\displaystyle k$ -se ajusta a $\displaystyle k$ -conjuntos tales que $\displaystyle F(X) \cap X = \emptyset$ .

Teniendo en cuenta esta $\displaystyle F$ podemos construir la biyección necesaria $\displaystyle f$ tomando $\displaystyle f(X) = [n] - F(X)$ , donde $\displaystyle [n] = \{1,2,\dots, n\}$ y estamos construyendo subconjuntos de $\displaystyle [n]$ .

Ahora, para construir la biyección $\displaystyle F$ . Escribe $\displaystyle 1,2,\dots n$ a lo largo de un círculo.

Ahora, dado un conjunto $\displaystyle X = \{x_1, x_2, \dots, x_k\}$ donde $\displaystyle x_1 \lt x_2 \lt \dots x_k$ .

Comienza en $\displaystyle x_1$ y recorrer el círculo en el sentido de las agujas del reloj, eligiendo el primer elemento que no esté en el conjunto $\displaystyle X$ (algo así como un hashing consistente, si eres programador). A continuación, vaya a $\displaystyle x_2$ y se va en el sentido de las agujas del reloj para recoger el primer elemento no recogido hasta el momento (y que no esté en $\displaystyle X$ ) y así sucesivamente.

Estos $\displaystyle k$ elementos que eligió de la forma $\displaystyle F(X)$ . Es fácil ver que $\displaystyle X \cap F(x) = \emptyset$ .

También podemos demostrar que $\displaystyle F(X) \neq F(Y)$ si $X \neq Y$ .

Si $\displaystyle X = \{x_1, x_2, \dots, x_k\}$ y $x_1 \lt x_2 \dots$ y

si $\displaystyle Y = \{y_1, y_2, \dots, y_k\}$ y $y_1 \lt y_2 \dots$

Entonces supongamos que $j \gt 1$ es el más pequeño tal que $\displaystyle x_j \neq y_j$ y asumir $\displaystyle y_j \lt x_j$ .

Ahora el algoritmo anterior habrá elegido $\displaystyle y_j$ para estar en $\displaystyle F(X)$ o elegiría diferentes números (para $\displaystyle F(X)$ y $\displaystyle F(Y)$ ) en el $\displaystyle j^{th}$ redonda.

Si no hay tal $\displaystyle j \gt 1$ , entonces los conjuntos sólo difieren en el elemento más pequeño, y en cuyo caso, la resultante $\displaystyle F$ Los conjuntos también serían diferentes.

---

Si no nos preocupa la construcción exacta, también podemos dar una prueba de existencia.

La existencia de una biyección puede demostrarse mediante el siguiente teorema:

Teorema: Cada $\displaystyle k$ -El grafo bipartito regular tiene una correspondencia perfecta.

Esto se puede demostrar por inducción en $\displaystyle k$ y utilizando Teorema de Hall .

Se construye un grafo bipartito con $\displaystyle k$ -como la partición de la izquierda y $\displaystyle n-k$ -sets como la partición correcta.

Vértice $\displaystyle L_i$ está conectado a $\displaystyle R_j$ si $\displaystyle L_i \subset R_j$ .

Este es un $\displaystyle \binom{n-k}{n-2k}$ gráfico bipartito regular.

Answer 2

He aquí una simple biyección. Haz una cadena de $n$ paréntesis tomando en la posición $i$ un paréntesis de apertura si $i$ es ausente del original $k$ y un paréntesis de cierre si $i$ está presente. Ahora ciertos paréntesis de la cadena coincidirán correctamente con otro, mientras que otros no. Dejemos que $S$ sea el conjunto de índices de paréntesis no coincidentes. Centrándonos en la subpalabra extraída en las posiciones de $S$ , cualquier paréntesis de apertura en la subpalabra viene después de cualquier paréntesis de cierre de la subpalabra, ya que de lo contrario habría al menos un par de paréntesis coincidentes en la subpalabra, en contra de su construcción. También hay $(n-k)-k=n-2k>0$ más paréntesis de apertura en la subpalabra que de cierre, ya que los pares coincidentes que se excluyeron no afectan a este equilibrio.

Ahora la biyección consiste en añadir a la $k$ subgrupo de la primera $n-2k$ elementos de $S$ que tienen un paréntesis de apertura (lo que significa que aún no están en el $k$ subconjunto). Esto convierte estos paréntesis en paréntesis de cierre. La clave de que se trate de una biyección es que este cambio no modifica el estado de no coincidencia de los paréntesis modificados. Por lo tanto, la misma construcción en el $n-k$ subconjunto producido producirá el mismo conjunto $S$ de índices de paréntesis no coincidentes, y ahora cambiando el último $n-2k$ paréntesis de cierre en los índices de $S$ reconstruirá la situación original (y la misma inversión se aplica también si se parte de un $n-k$ subconjunto, hace un $k$ y luego un $n-k$ subconjunto de nuevo, mostrando que uno realmente tiene dos procedimientos mutuamente inversos).