Sea$A$ un subconjunto de elementos del conjunto$101$

Question

Deje $A$ ser $101$-elemento subconjunto del conjunto $S=\{1,2,\ldots,10^6\}$. Para cada una de las $s\in S$ deje $$A_s = A+s = \{a+s \mid a\in A\}$$ Demostrar que no existe $B\subset S$ tal que $|B|=100$ y los juegos en una familia $$\{A_b \mid b\in B\}$$ son pares distintos.

---

Es una siguiente prueba correcta?

Deje $B$ ser máxima de dicha serie que pone en $\{A_b \mid b\in B\}$ son disjuntos a pares y deje $|B|=k$.

A continuación, para cada una de las $b'\in B'= S\setminus B$ existe $b \in B$ que $A_b\cap A_{b'}\ne \emptyset$, es decir, existe $a_1,a_2\in A$ , de modo que $$b' = a_1-a_2+b\;\;\;\;\;\;\;\;\;(*)$$

Ahora hacer un bipartito gráfico con $B'$ en el lado izquierdo y en el lado derecho: $$C:= \{(a_1,a_2,b)\mid a_1,a_2\in A, a_1\ne a_2, b\in B\}$$

Claramente $ |C| = 101\cdot 100\cdot k$ e $|B'| = 10^6-k$.

Conecte $b'\in B'$ con $(a_1,a_2,b)\in C$ fib $b' = a_1-a_2+b$. Entonces es claro que cada triple dispone de grado en la mayoría de las $1$ y cada una de las $b'$ ) por $(*)$ grado, al menos, $1$. Por la doble contabilización, tenemos: $$ 10^6-k=|B'|\leq |C| = 101\cdot 100\cdot k$$

por lo $$k\geq {10^6\over 101\cdot 100+1}>99$$

Por lo $k\geq 100$ y hemos terminado.

---

Aparte de una prueba de verificación, estoy interesado en probabilístico solución de este problema.

Voy a ofrecer una recompensa para un probabilística de la solución.

Answer 1

La prueba está bien.

Una más generales de instalación para la prueba sería considerar la gráfica de $G$ con conjunto de vértices $S$ y un borde entre el $x, y\in S$ siempre $A_x \cap A_y = \varnothing$. (Puede ser más conveniente poner un borde entre el $x,y$ por cada elemento de a$A_x \cap A_y$, lo $G$ un multigraph.) Entonces estamos buscando un conjunto independiente de $100$ vértices en $G$.

Su gráfico bipartito entre $B'$ e $C$ tiene una especie de encarnación dentro de la $G$. Considerar el subgrafo de $G$ que consta de todos los bordes entre las $B$ e $B'$. Cada $b \in B$ tiene el grado $101 \cdot 100$ en $G$ ($b$ tiene un borde a $b + a_1 - a_2$ por cada $a_1, a_2 \in A$ con $a_1 \ne a_2$), y estos bordes deben ir a $B'$, desde el $B$ es independiente. Cada $b' \in B'$ tiene al menos $1$ borde a $B$, debido a $B$ es un conjunto independiente maximal. Por lo que el número de aristas entre $B$ e $B'$ es $101 \cdot 100 \cdot |B|$, pero también es, al menos, $|B'| = 10^6-|B|$. Por lo tanto $$ 10100 |B| \ge 10^6-|B| \ffi |B| \ge \frac{10^6}{10101} > 99. $$ Esta es, esencialmente, una reafirmación de su argumento: en lugar de $10100$ elementos de $C$ con grado de $1$ por cada $b \in B$, se combinan en un único vértice $b$ con grado de $10100$.

De manera más general, esto demuestra que en un grafo (o multigraph) $G$ con $n$ vértices y grado máximo $\Delta(G)$, hay un conjunto independiente de tamaño $\frac{n}{\Delta(G)+1}$.

El método de probabilidades puede ser utilizado para obtener un límite que es mejor, en general, pero no una mejora en este problema. En general, podemos llegar a $\frac{n}{d+1}$, donde $d$ es el promedio de grado en $G$. Pero aquí, el grado medio es también bastante cerca de a $10100$, así que esto no es de mucha ayuda.

Aquí está el argumento probabilístico. Al azar permutar los elementos de $S$ como $b_1, b_2, \dots, b_{10^6}$, e ir a través de ellos uno a la vez para crear un conjunto independiente $B$. Para cada una de las $b_i$, agregar $b_i$ a $B$ si cada elemento de la forma $b_i + a_1 - a_2$ (con $a_1, a_2 \in A$ e $a_1 \ne a_2$) viene después de la $b_i$ en nuestro ordenamiento al azar.

Esto está garantizado para crear un conjunto independiente: si $b_i + a_1 - a_2 = b_j$, entonces cualquiera de las $i<j$ (y, entonces, tenemos la garantía de que no se han recogido $b_j$) o $i>j$ (y, entonces, tenemos la garantía de que no se han recogido $b_i$). Para cualquier $b \in S$: $b$ y su en-la mayoría-$10100$ elementos adyacentes, cada uno tiene la misma probabilidad de llegar por primera vez en el ordenamiento al azar, y es $b$ sí, con probabilidad de $\frac{1}{10101}$, caso en el cual añadimos a $B$.

Por lo que el tamaño esperado de $B$ al menos $\frac1{10101}|S| = \frac{10^6}{10101} > 99$, como antes, por lo que en algunos ordenamiento al azar produce un $B$ de tamaño, al menos, $100$.