Encontrar el número mínimo de alumnos

Question

Hay $p$ comisiones en una clase (donde $p \ge 5$), cada uno compuesto de $q$ de los miembros (donde $q \ge 6$).No hay dos comités se les permite tener más de 1 estudiante en común. ¿Cuál es el mínimo y el máximo número posible de estudiantes?

Es fácil ver que el número máximo de estudiantes es de $pq$,sin embargo no estoy seguro de cómo encontrar el número mínimo de alumnos.Alguna idea?

AÑADIDO estoy agregando el dado opciones de respuesta:

$1) \quad pq - \binom{q}{2}$

$2) \quad pq - \binom{p}{2}$

$3) \quad (p-1)(q-1)$

Answer 1

Para $1\leq i\leq p$, vamos a $C_i$ el conjunto de los estudiantes en el $i$th comité. A continuación, por medio de la inclusión-exclusión, o más exactamente Boole de las desigualdades, tenemos $$\sum_i|C_i|-\sum_{i<j}|C_i C_j|\leq |C_1\cup C_2\cup\cdots \cup C_p|\leq \sum_i |C_i|.$$

De las restricciones del problema, esto significa $$pq-{p\choose 2}\leq \#\mbox{ students}\leq pq.$$

Answer 2

Creo que el siguiente teorema puede ser relevante:

Teorema. Deje $\mathcal{F}$ ser una familia de subconjuntos de a $\{1, \dots , n \}$ con la propiedad de que $|A \cap B| = 1$ todos los $A,B \in \mathcal{F}$. A continuación,$|\mathcal{F}| \leq n$.

También este teorema puede ser pertinente.

Answer 3

Para el caso en que $p \le q+1$ a un acuerdo que produce el mínimo número de estudiantes que pueden describirse de la siguiente manera.

Deje $P = \{\langle m,n \rangle:1 \le m \le p, 1 \le n \le q+1\}$, y deje $S = \{\langle m,n \rangle \in P:m < n\}$. Si $P$ es considerado como un $p \times (q+1)$ cuadrícula, $S$ es la parte de la letra por encima de la principal de 'diagonal'. Las células en $S$ son estudiantes; el $k$-th el comité se compone de esas células en $S$ que están en la fila $k$ o en la columna $k$. Más formalmente, para $1 \le k \le p$ vamos $$\begin{align*}C_k &= \{\langle m,n \rangle \in S:m=k \lor n=k\}\\ &= \{\langle k,n \rangle:k+1 \le n \le q+1\} \cup \{\langle m,k \rangle:1 \le m \le k-1\};\end{align*}$$ clearly $\vert C_k \vert = q+1-k+k-1=q$, and if $1 \le i < k \le p$, $C_i \cap C_k = \{\langle i,k \rangle\}$. Since every pair of committees shares a different student, this arrangement must minimize the number of students, so we need only calculate $\vert S \vert$.

Columnas $2$ a través de $p$ de la cuadrícula contener $\sum_{k=1}^{p-1} k = \binom{p}{2}$ de las células, y el resto de $q+1-p$ columnas contienen $p(q+1-p)$ de las células, por lo que $$\begin{align*}\vert S \vert &= \binom{p}{2} + p(q+1-p)\\ &= \frac{p^2 - p}{2} + pq + p - p^2\\ &= pq - \frac{p^2-p}{2}\\&= pq - \binom{p}{2}. \end{align*}$$

Al $p > q+1$ el mismo método funciona, pero no es posible obtener de cada par de los comités de la superposición. La primera forma de $\left\lfloor \frac{p}{q+1}\right\rfloor$ juegos de $q+1$ comités de cada uno. Cada juego requiere de $(q+1)q-\binom{q+1}{2}=\binom{q+1}{2}$ a los estudiantes, y de los comités en diferentes conjuntos deben ser disjuntos, por lo que esto representa para $\left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2}$ de los estudiantes. El resto de los $r = p-(q+1)\left\lfloor \frac{p}{q+1}\right\rfloor$ comités, a continuación, requieren de otro $rq - \binom{r}{2}$ a los estudiantes, para un gran total de $$\begin{align*} \vert S \vert &= \left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2} + rq - \binom{r}{2}\\ &= \left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2} + \left(p-(q+1)\left\lfloor \frac{p}{q+1}\right\rfloor\right)q - \binom{r}{2}\\ &= pq - \left\lfloor \frac{p}{q+1}\right\rfloor \binom{q+1}{2} - \binom{r}{2} \end{align*},$$, que no aparece para simplificar en gran medida.

Veo que esta es esencialmente la de Alex de la solución, pero se mostró un poco más concreta.

Answer 4

Bien, supongo que es la pregunta, es decir, para algún valor fijo de $p$$q$, ¿cuál es el número mínimo y máximo de estudiantes que pueden tener. Si es así, estoy de acuerdo en que el número máximo es de $pq$, como acabamos de no dejar que ninguno de los alumnos se superponen en cada una de las comisiones. También ha sido un tiempo desde que he hecho algo como esto, así que esperemos que no estoy haciendo un tonto error!

Para el mínimo, desea maximizar la superposición. Vamos a empezar con el más simple(?) caso, donde$p=5$$q=6$. Llame a los comités $p_1,\ldots,p_5$. El solapamiento máximo que puede ocurrir, es de 4 estudiantes de un comité de cada uno de los miembros de los otros 4 los comités, por tanto, con el solapamiento máximo posible, el número de estudiantes que requieren es \begin{align*} 30 - 4 - 3 - 2 - 1 = 20. \end{align*}

Lo que si cambiamos $q = 7$? Nada de cambios, como los comités han superpuesto tanto como sea posible ya, así que para cualquier $q \geq 6$, el número de alumnos es \begin{align*} pq - \sum_{i=1}^{p-1} i = pq - \frac{p(p-1)}{2}. \end{align*}

Por supuesto, esto sólo "la mitad" de lo que queremos. Lo que si dejamos $q$ a los 6, pero el conjunto de $p=6$? Ahora hay toda una comisión donde podemos superposición de los estudiantes, así que se superponen como muchos como sea posible, tenemos que el número mínimo de alumnos es \begin{align*} 36 - 5 - 4 - 3 - 2 - 1 = 21. \end{align*}

Como el número de comités aumenta, podemos ser capaces de se superpone a más estudiantes. Supongamos $p=7$$q=6$. Nos encontramos con el número mínimo de alumnos es \begin{align*} 42 - 6 - 5 - 4 - 3 - 2 - 1 = 21. \end{align*} El mismo que el anterior! Pero si queremos añadir uno más, el comité, no podemos superposición de alguna de las presentes estudiantes, por lo que debemos tener otro $q$ añadido en. En general, establezca $m = \lfloor p/(q+1) \rfloor$. Requerimos, mínimamente \begin{align*} m\left(q(q+1) - \sum_{i=1}^q i\right) + \left(rq - \sum_{i=1}^{r-1} i\right) \end{align*} los estudiantes, donde $r$ es el resto al $p$ se divide por $q+1$. Por supuesto, las cantidades pueden ser evaluados para darle una expresión sin la $i$'s si lo deseas.

Answer 5

Aquí es un límite inferior de un doble estándar de contar el argumento. Deje que el número de estudiantes se $n$. Vamos a contar triples $(s,c_1,c_2)$ donde $c_1$ $c_2$ son distintos comités que contiene estudiante $s$. El recuento de estas tripletas por primera fijación $s$ o de la primera fijación de $c_1$ $c_2$ y, a continuación, utilizando la media cuadrática de la desigualdad, obtenemos la desigualdad $$n{pq/n \choose 2}\leq {p \choose 2}$$ $$n\geq \frac{pq^2}{p+q-1}$$ La igualdad sólo puede mantener cuando cada par de comités se cruzan en exactamente uno de los estudiantes, y de cada estudiante en el mismo número de comités. Estos son los diseños de bloque con $\lambda=1$. Al $n=p$, estos son los planos proyectivos. Tal vez alguien que sepa más acerca de los diseños de bloque que yo puede dar construcciones para otros casos.