Una identidad combinatoria.

Question

Deje $n \in \mathbb N$ $X_1,\ldots,X_n$ ser subconjuntos de a $\{1,\ldots,n\}$ que hay algunos $p$ tal que $\forall i\in \{1,\ldots,n\}, |X_i|=p$.

Supongamos también que hay algunos $q$ tal que $i\neq j \implies |X_i \cap X_j|=q$.

Demostrar que $p^2=p+(n-1)q$.

He intentado algo con una incidencia de la matriz y se reduce a probar que su determinante es $p^2(p-q)^{(n-1)/2}$, pero no puedo demostrar que

EDIT: El problema como se dijo, es imperfecta. Se debe agregar que cada una de las $i$ aparece en exactamente $p$ de la $X_j$

Answer 1

Esta es una prueba para el caso de que cada una de las $i \in \{1,2,\ldots,n\}$ está contenido en $p$ de la $X_j$. Como se señaló en los comentarios, el resultado no es cierto en general de otra manera.

Que nos permiten contar el número de tripletes $(i,j,k) \in \{1,2,\ldots,n\}^3$ con la propiedad de que $i \neq j$, $k \in X_i$ y $k \in X_j$.

La elección de $i$ $j$ primero y, a continuación, eligiendo $k \in X_i \cap X_j$ se puede hacer en $n(n-1)q$ maneras.

La elección de $i$ en primer lugar, a continuación, $k \in X_i$ y, a continuación, $j$ tal que $k \in X_j$ se puede hacer en $np(p-1)$ formas, debido a $k$ está contenido en $p-1$ conjuntos distintos de $X_i$.

Llegamos a la conclusión de que tanto $n(n-1)q$ $np(p-1)$ contar el número de tripletes, por lo tanto $n(n-1)q=np(p-1)$. Este rendimientos $(n-1)q = p(p-1)$, como se desee.

Answer 2

Demuestro $p^2 \le p+(n-1)q$ en general y la igualdad ocurre si, y sólo si @user133281 la hipótesis es verdadera:

Definir una matriz $A =(a_{ij})$ donde $a_{ij} = 1$ si $j \in X_i$ e lo contrario $a_{ij} = 0$, entonces la condición dada se puede escribir como

$$AA^{T} = \left( \begin{array}{ccc} p & q & \cdots & \cdots &q \\ q & p & q & \cdots & q \\ \vdots & \vdots & \vdots & & \vdots \\ q & q & q & \cdots & p \end{array} \right) $$

Denotar $b_i = \sharp\{j, i\in X_j\}$, entonces al multiplicar ambos lados de la anterior matriz identidad por el vector $v = (1,1,1,\cdots, 1)^T$ informática y de los elementos de la suma de ambos resultados, podemos mostrar a $$\sum_{i=1}^n b_i^2 = n(p+(n-1)q)$$ (Observación de que la $A^T v = (b_1, b_2, \cdots, b_n)^T$ y los elementos de $A(b_1, b_2, \cdots, b_n)^T$ resume a $\sum_{i=1}^n b_i^2$)

Y, obviamente, también tenemos $\sum_{i=1}^n b_i = np$.

Desde $(\sum_{i=1}^n b_i^2 )(n) \ge (\sum_{i=1}^n b_i )^2$,$ n^2(p+(n-1)q) \geq n^2p^2$, lo $p^2 = p+(n-1)q$ si y sólo si todos los $b_i$'s son iguales, es decir, $b_i = p, \forall i$