Variación difícil del problema del comité.

Question

Es un ejercicio trivial en el principio del palomar para demostrar que si una organización contiene $m$ personas y formas distintos comités de $n$ cada uno de los miembros, en la mayoría de los $$\bigg \lfloor \frac{m}{n} \bigg\rfloor$$ los comités pueden ser formados.

Sin embargo, recientemente he intentado un aparentemente simple variación de este problema: ¿y si los comités no necesita ser distinto, pero no hay dos comités pueden compartir más de un miembro.

Parece que otro ejercicio fácil en el principio del palomar, pero he sido incapaz de encontrar una fórmula para que el mayor número de comités en términos de $m$ e $n$. ¿Alguien sabe de esta fórmula?

Answer 1

Este es un problema bien conocido que a menudo me encuentro en diferentes formas. Por $m$ e $n$ deje $c=c(m,n)$ ser el mayor número posible de los comités. Hasta donde yo sé, fórmulas exactas para $c(m,n)$ son conocidos sólo en los casos en particular, para las pequeñas $m,n$ y dos series infinitas. Hay ${m\choose 2}$ pares diferentes de los miembros de la organización. Por otro lado, cada comité brinda ${n\choose 2}$ tales pares y no pares pueden ser proporcionados por los dos comités. Esto da una cota superior de a$c\le\frac{m(m-1)}{n(n-1)}$. Este límite superior es exacta si existe una Steiner sistema de $S(2,n,m)$. Para valores particulares de $m,n$ su construcción se basa en la finitos planos proyectivos. Pero esos planos son más de un campo finito de una orden de $q$, que existe iff $q$ es una potencia de un primo, y no se conocen otros $q$ para que exista una Steiner sistema de $S(2, q, q^2)$ (o, equivalentemente, $S(2,q+1,q^2+n+1)$). Sin embargo, cuando se $m$ está cerca de a $n^2$ este enfoque proporciona un lugar apretado asintótica límite inferior de $c(m,n)$, porque para suficientemente grande $n$ existe un número primo $n-n^{0.525}\le q\le n$ (ver el artículo "La diferencia entre los números primos consecutivos II" por
R. C. Baker, G. Harman, y J. Pintz). Para la estimación de $c(m,n)$ para el hormigón $m$ e $n$ solemos elegir un básico comité patrón proporcionado por un finito proyectiva del plano y, a continuación, tratar de mejorar la construcción. El límite superior, a veces, puede ser mejorado por más sutil y complicado estimaciones. Por ejemplo, una recompensa pregunta pregunta acerca de mínimo $m$ tal que $c(m,10)\ge 40$. Los límites actuales son $74\le m\le 85$.

Answer 2

Para el límite inferior, puede formar aproximadamente el doble del número de comités de los distintos casos. Dividir a la gente en grupos de tamaño $\binom{n+1}2$, ignorando las sobras. Identificar a las personas de cada grupo con las aristas de un grafo completo en $n+1$ vértices. Para cada vértice de la gráfica, para formar un comité que consiste en la $n+1$ bordes de la reunión en ese vértice. Habrá $n+1$ comisiones por cada grupo de $\binom{n+1}2$ de las personas, para un total de $$ (n+1)\cdot\left\lfloor \frac{m}{\binom{n+1}2}\right\rfloor\approx \frac{2m}n\;\text{ comités.} $$