Sea $A$ sea un conjunto finito de números enteros no negativos y escribamos $I_k$ para el conjunto ${0,1,\ldots,k-1}$ . Formar todas las posibles intersecciones l-wise $(A+k_1)\cap \ldots \cap (A+k_l)$ donde cada $k_i$ recorre todos los valores del conjunto $I_k$ (lo que nos da $k^l$ de dichas intersecciones). Dado un número entero $0<t<|A|$ Quiero maximizar el número de intersecciones con una cardinalidad de al menos $t$ . ¿Es cierto que el conjunto óptimo $A$ es $\{0,1,\ldots,|A|-1\}$ ?
Respuesta
¿Demasiados anuncios?
Bryan
Puntos
256
Esto es no cierto sin algunas suposiciones adicionales, incluso en el caso más sencillo en el que $l=2$ y $t=1$ .
En este caso se cuentan los pares $(k_1,k_2)\in[0,k-1]^2$ con $(A+k_1)\cap(A+k_2)\ne\varnothing$ es decir, con $k_1-k_2\in A-A$ . Consideremos, por ejemplo, la situación en la que $n:=|A|\approx 2k^{1/2}$ . Si $A$ es un bloque de $n$ enteros consecutivos, entonces para $k_1-k_2\in A-A$ para sostenerte necesitas $|k_1-k_2|<n$ y hay menos de $2nk\approx 4k^{3/2}$ pares $(k_1,k_2)$ con esta propiedad. Al mismo tiempo, si en su lugar elige $A$ tener $[-k,k]\subseteq A-A$ (lo que es posible teniendo en cuenta la hipótesis $n:=|A|\approx 2k^{1/2}$ ), entonces todos $k^2$ pares posibles $(k_1,k_2)$ satisfará $k_1-k_2\in A-A$ .
