Pregunta acerca de los miembros de los conjuntos de

Question

Deje $A_1,A_2,...,A_n$ se establece con $k$ miembros $A_i$ por cada $1\le i\le n$. Supongamos que el $A_i$ satisfacer:

1) $|A_i\cap A_j| = 1$ todos los $i\ne j$,

2) $A_1\cap A_2\cdots\cap A_n =\emptyset$.

¿Cuál es el mayor $n$ por cada $k\in \mathbb{Z}^+$?

Alguien me dijo que el mayor $n$ $(k-1)^2+k$ al $k=1,2,3,4$. ¿Cómo se puede demostrar esto?

Answer 1

No he venido para arriba con una construcción en general, pero creo que la respuesta es $n=k^2-k+1$. Voy a demostrar que $n \leq k^2-k+1$. Voy a editar en la construcción en un tiempo cuando la pongo.

WLOG deje $A_1=\{1, 2, \ldots , k\}$, y deje $x_a$ el número de $j \not =1$ tal que $a \in A_j$ donde $1 \leq a \leq k$.

Observar que si $x_a \geq k$, entonces el WLOG deje $a \in A_{j}$$2 \leq j \leq x_a+1$.

Por la condición 1), cada una de las $A_j, 1 \leq j \leq x_a+1$ sólo ha $a$ en común.

Por la condición 2), $x_a+1<n$. Considere la posibilidad de cualquier $l>x_a+1$, $A_l$ no contiene $a$. Por lo tanto $A_l \cap (A_j \setminus a)=\{a_j\}, 1 \leq j \leq x_a+1$ donde $a_j$ son distintos.

Por lo tanto,$|A_l| \geq x_a+1 \geq k+1$, una contradicción.

Por lo tanto $x_a \leq k-1$, lo $n=1+\sum\limits_{a=1}^{k}{x_a} \leq 1+k(k-1)$.

Answer 2

Podemos seguir a @Ivan de la respuesta, para dar una construcción con $k(k-1)+1$ conjuntos. Se ha demostrado que cada elemento no puede estar presente en más de $k$ conjuntos, esta construcción de cada elemento que ocurren en exactamente $k$ conjuntos.

Deje $A_1 = \{1,2,\ldots ,k\}$. Dejar que la próxima $k-1$ conjuntos de $A_2, A_3, \ldots , A_k$ contienen el elemento $k$. Como ahora todos tienen un elemento común de $k$, el resto de las $(k-1)^2$ elementos deben ser distintos. Deje que ellos se $k+1, k+2, \ldots , k+(k-1)^2$, distribuidos entre las $k-1$ define de forma secuencial, es decir, para $j=2,3, \ldots k$, $A_j = \{j(k-1)+2, j(k-1)+3, \ldots , j(k-1)+k\}$.

El resto de los $(k-1)^2$ conjuntos de $A_{i(k-1)+j+1}$ (donde $i,j=1,2, \ldots , k-1$) son descritos por

1. $i \in A_{i(k-1)+j+1}$
2. $p,q \in A_{i(k-1) + j+1} \Leftrightarrow (p-q) \mod (k+j-2) \equiv 0$

es decir, $A_{i(k-1)+j+1} = \{[i+r(k+j-2)] \mod ((k-1)^2 + k): r=0,1,\ldots ,k-2\}$. Es fácil comprobar que estos conjuntos de satisfacer la necesaria restricciones.

Answer 3

Alguien me dijo que el mayor $n$ es
$(k−1)^2+k$ al $k=1,2,3,4$. ¿Cómo se puede demostrar esto?

Que es el obligado de tomar el de los conjuntos de la $q^2+q+1$ líneas en un plano proyectivo con las coordenadas de la esfera con $q$ elementos, con $q=k-1$. El campo finito existe al $k-1$ es una fuente primaria de energía, que contempla los casos $k=3,4,5,6$. Su informante era el pensamiento de esta construcción para el caso especial donde $q$ es el primer modo que uno puede utilizar enteros mod $q$ como coordenadas en lugar de hablar sobre campos finitos. Esto funciona para $q \leq 3$ o $k=3,4$. No hay ninguna solución para $k=1$ y la solución para $k=2$ satisface el mismo límite. Esto explica por qué su origen dio la respuesta a a $k=4$ solamente.