Desafiante Contando problema

Question

Tengo un conteo problema para el trabajo que hemos estado tratando de resolver un poco ahora, y finalmente han llegado aquí en busca de ayuda. Aquí está el problema:

Dado 100 personas, se dividió a las 100 personas en grupos de 4. Ahora tenemos 25 grupos de 4 personas. La pregunta es, ¿cuántas veces se puede el 100 personas, se divide en 25 grupos de 4, para que nadie está en un grupo con la misma persona dos veces?

Idealmente, estamos buscando una solución general para el problema. Hemos trabajado un par de versiones más pequeñas con la mano. Por ejemplo, para 16 personas divididas en grupos de 4, se pueden formar grupos de 3 tres veces.

Alguna idea?

Answer 1

Este es el Social Golfista Problema. Estás buscando Resolver Steiner Cuádruple Sistemas. La más alta conocida de la solución yo sé que sobre es para 32 golfistas de juego en foursomes por 10 días.

Los nombres de lo que en realidad necesita ser cuidado para que son un poco disperso. Por ejemplo, el 36 golfistas en foursomes puede jugar de 11 días. Este es un 4-RGDD de tipo $2^{18}$.

En teoría, el 100 golfistas en su grupo se podría dividir en foursomes 33 (1 persona + 3x33) veces, pero que sería una perfecta cubierta, y los que son bastante bien conocidos. No se trata de un perfecto cubre se enumeran en el Manual de la Combinatoria de los Diseños, así que es probable que algo complicado, o nonperfect y más complicado.

La Jolla Cubriendo Repositorio se detiene en 99 puntos. Hay una C(99,4,2) = 817 diseño... si esto se puede resolver (splittable en grupos que cubren 1-100), 817/25 = 32.65, así que tal vez usted podría conseguir 32 divisiones.

Tal vez el Diseño de Siglo es resoluble. En ese caso, tienes una solución perfecta. Que papel tiene varias referencias para este diseño en particular. En cualquier caso, usted va a encontrar una respuesta dentro de los métodos combinatorios mucho más rápido que con cualquier tipo de acercamiento de fuerza bruta.