Encontrar el número mínimo de miembros

Question

He estado trabajando en el problema siguiente

Para cada emisión en el Azul de la asociación, una comisión de 10 miembros (pertenecientes a la Azul) se formó con el fin de resolver el problema. La única condición es

No puede haber dos comisiones de haber más de un miembro en común

El Azul de la asociación se ha formado este año 40 comisiones.

¿Cuál es la mínima cantidad de miembros en el Azul de la asociación?

Sólo he encontrado las siguientes

Para cualquier comisión que se pueden formar a$\binom{10}{2}=45$ parejas diferentes y ninguno de ellos puede aparecer en otra comisión.

Ya que el 40 diferentes comisiones que se forman, el número mínimo de pares es $45\times 40=1800$.

Denotar por $n$ el número de miembros. Por lo tanto $$\binom{n}{2}≥1800\Rightarrow n>60$$

$$$$

La cantidad mínima de miembros tiene que ser de 100 o menos.

Se puede observar la distribución por 100 de los miembros aquí

Mi pregunta:

Es 100 la respuesta o es que hay cada vez una menor cantidad posible de miembros? Si es así, ¿cómo puedo demostrarlo?

Answer 1

Deje $i$ denotar cada uno de los miembros de Azul y asumir que no se $N$ miembros en total, es decir, $i=1,2,\cdots, N.$ Y deje $j=1,2,\ldots, 40$ denotar cada una de las 40 de la comisión. Vamos a mostrar que el $N\geq 82$.

Consideremos el conjunto $$ S=\{(i,j,k)\;|\;1\leq i\leq N, 1\leq j<k\leq 40, i\text{ pertenece a }j,k\text{-ésimo de la comisión.}\}. $$ Let $d_i$ denote the number of commissions that $i$ joined. We will calculate $|S|$ usando un doble método de la sumación. En primer lugar, tenga en cuenta que $$ |S|=\sum_ {i,j,k)\S}1 = \sum_{1\leq j<k\leq 40} \sum_{i: i,j,k)\S}1\leq \sum_{1\leq j<k\leq 40}1=\binom{40}{2}, $$ since for each $j<k$, there is at most one $i$ en común. Por otro lado, $$ |S| = \sum_{1\leq i\leq N} \sum_{(j,k):(i,j,k)\S}1 = \sum_{1\leq i\leq N} \binom{d_i}{2}, $$ since for each $i$, the number of pairs $(j,k)$ that $i$ joined is $\binom{d_i}{2}$. También tenemos $$\sum_{1\leq i\leq N}d_i = 400,$$por la asunción.
Por último, tenga en cuenta que la función de $x\to \binom{x}{2} = \frac{x^2-x}{2}$ es convexa. Por lo tanto, tenemos que $$ \binom{40}{2}\geq |S|=\sum_{1\leq i\leq N} \binom{d_i}{2}\geq N\binom{\frac{\sum_i d_i}{N}}{2}=N\binom{\frac{400}{N}}{2}. $$ Esto nos da la enlazado $$ 40\cdot 39 \geq 400\cdot(\frac{400}{N}-1), $$y por lo tanto $$ N \geq \frac{4000}{49}\geq 81.63. $$ This establishes $N\geq 82$. Sin embargo, no estoy seguro de si esta obligado es apretado. Espero que esto ayude.

$\textbf{Note:}$ Si $N=82$ es apretado, entonces el argumento anterior implica que $d_i$'s de distribución es casi concentrada en $\overline{d} = 400/82 \sim 5$.

Answer 2

Esto es sólo una respuesta parcial. Voy a demostrar que $85$ miembros basta; no sé si $85$ es el mínimo.

Recordemos que un plano proyectivo de orden $n$ si $n$ es una fuente primaria de energía: se ha $n^2+n+1$ puntos y $n^2+n+1$ líneas, cada línea tiene $n+1$ puntos, y hay $n+1$ líneas a través de cada punto; cualquier par de líneas reúne en un único punto, y cualquier par de puntos determina una única línea.

Considere la posibilidad de un plano proyectivo de orden $9$; ha $9^2+9+1=91$ puntos y $91$ líneas; hay $10$ puntos en cada línea y $10$ líneas a través de cada punto. Un conjunto de puntos en posición general , si no en tres puntos son colineales. Tenga en cuenta que, si tenemos un conjunto de $t$ puntos en posición general, luego las líneas determinada por los puntos (tomados de dos en dos) cubren un total de más de $t+8\binom t2$ puntos; mientras $t\le5$ el número de cubiertos número de puntos es en la mayoría de las $5+8\binom52=85\lt91$, por lo que podemos añadir otro punto de la serie y todavía en posición general. Así, podemos encontrar un conjunto $S$ de $6$ puntos en posición general.

Deje que los miembros de Blue asociaciones de la $91-6=85$ puntos que no están en $S$. Las comisiones son las líneas que no cumplen con las $S$; tienen $10$ miembros cada uno, y cualquiera de los dos tienen exactamente un miembro en común. Finalmente, por la en-y-fuera de la fórmula, el número de comisiones es $$91-\binom61\cdot10+\binom62\cdot1=46.$$

P. S. Deje $m$ es el mínimo número posible de miembros. Me mostró por encima de ese $m\le85$. Por otro lado, tengo una pequeña mejora en su límite inferior $m\ge61$.

Supongamos que el $i^\text{th}$ pertenece a $d_i$ comisiones; a continuación, $$\sum_{i=1}^md_i=400$$ desde allí se $40$ comisiones con $10$ cada uno de los miembros. Por otra parte $d_i\le9$ desde $m\le85\lt91$. Deje $k=|\{i:d_i\ge5\}|$. Entonces $$400=\sum_{i=1}^md_i\le4(m-k)+9k=4m+5k\le340+5k,$$ de dónde $k\ge12$; es decir, hay al menos $12$de los miembros que están en, al menos, $5$ comisiones. Elegir dos miembros de la $i$ e $j$ que están en, al menos, $5$ comisiones.

Caso 1. Hay una comisión que contiene tanto $i$ e $j$.

En primer lugar, hay $10$de los miembros de la comisión que $i$ e $j$ a que ambos pertenecen. La próxima $i$ pertenece a $4$ más comisiones, con $36$ miembros adicionales. Finalmente, $j$ pertenece a $4$ más comisiones, cada una de las cuales contiene a lo más uno de los miembros de cada una de las $5$ comisiones que agrupa $i$, y al menos $5$ miembros que no han sido contados, sin embargo, para un total de $20$ nuevos miembros. Esto demuestra que $m\ge10+36+20=66$.

Caso 2. No hay comisión que contiene tanto $i$ e $j$.

En este caso, un argumento similar muestra que $m\ge67$.

Esto demuestra que $m\ge66$. La combinación de este con el límite superior se muestra anteriormente, hemos $$66\le m\le85.$$

Answer 3

He aquí una respuesta parcial que aumenta el límite inferior de cualquiera (no necesariamente la óptima) solución a $m\ge 74$.

Supongamos que existe una solución con $m$ miembros y sabemos que hay dos miembros de cada una de las en $l+1$ comisiones, a continuación, $$m\ge 9(l+1)+(8-l)(l+1)+2.$$ Esto es debido a que si se es miembro de una es $\ge l+1$ comisiones, cada comisión debe ser llenado con $9$ nuevos miembros, ya que estos $l+1$ comisiones ya han solapamiento máximo. Para que las comisiones que los miembros de dos, cada una de las necesidades de $9$ más miembros para ser tomados en cuenta. Nosotros no podemos tener ningún solapamiento entre estas comisiones, porque ellos ya tienen solapamiento máximo (que es miembro de dos). Podemos, en el mejor de elegir uno de los miembros de cada grupo con los miembros de uno, dándonos $l+1$ miembros, pero el otro $9-(l+1)=8-l$ son nuevos. Esto le da a $9(l+1)+(8-l)(l+1)$ miembros aparte de los dos que hemos empezado. (Tenga en cuenta que esta es la mejor obligado en $l$ posible).

Ahora, supongamos $m$ de los miembros tiene una solución para el problema. Deje $d_i$ ser de cuantas comisiones de la $i$-ésimo miembro. Primera nota de que $m\ge 9d_i+1$ por cada $i$, lo $d_i\le \lfloor (m-1)/9\rfloor$. Deje $k_l=|\{i\; :\; d_i>l\}|$. Entonces $$400=\sum_{i=1}^md_i\le l(m-k_l)+\lfloor (m-1)/9\rfloor k_l.$$ Por lo tanto $$k_l\ge \frac{400-lm}{\lfloor (m-1)/9\rfloor -l}.$$ Desde $k_l$ es un número entero, si $\frac{400-lm}{\lfloor (m-1)/9\rfloor -l}>1$ entonces $k_l\ge 2$, lo que significa que hay al menos $2$ miembros en al menos $l+1$ comisiones de modo por la mencionada $m\ge 9(l+1)+(8-l)(l+1)+2$. Tenga en cuenta que $\frac{400-lm}{\lfloor (m-1)/9\rfloor -l}>1$ exactamente cuándo $\frac{400-\lfloor (m-1)/9\rfloor}{m-1}>l$. Por lo tanto, tenemos que para todo $$\frac{400-\lfloor (m-1)/9\rfloor}{m-1}>l$$ tenemos $$m\ge 9(l+1)+(8-l)(l+1)+2.$$ Para que esto sea satisfecha da $$m\ge 74.$$