Generalización:
Tenemos [math] n \ in \ mathbb {N} [/ math] personas y se nos da una [math] k \ in \ mathbb {N} [/ math], de modo que [math] k \ leq n [/ matemáticas] y [matemáticas] n \ equiv 0 \ mod {k} [/ matemáticas]. Deseamos dividir a las personas exactamente [matemáticas] \ frac {k} {n} \ binom {n} {k} = \ binom {n-1} {k-1} [/ matemáticas] veces, cada partición contiene exactamente [ math] \ frac {n} {k} [/ math] subconjuntos de tamaño [math] k [/ math] cada uno. Queremos hacer esto para que no se repita ningún subconjunto [math] k [/ math], y todos los subconjuntos [math] \ binom {n} {k} [/ math] sean golpeados después del [math] \ binom {n -1} {k-1} [/ math] particiones.
Para nuestra pregunta específica, [matemáticas] n = 18 [/ matemáticas] y [matemáticas] k = 3 [/ matemáticas].
- Si sabemos cómo funciona un algoritmo de hash de contraseña en particular, ¿por qué no podemos simplemente crear una contraseña que genere el mismo hash?
- ¿Cuál es la diferencia entre árboles binarios completos y completos?
- ¿Se puede aplicar BFS a gráficos ponderados?
- ¿Cuál es la razón por la que el conjunto de todos los enteros contiene 0?
- ¿Por qué no hay implementación de montón de Fibonacci en la API Java estándar?
Responder:
En general, la respuesta proviene del teorema de Baranyai. De acuerdo con este teorema, si [math] n \ equiv 0 \ mod {k} [/ math], siempre hay una manera de dividir [math] n [/ math] personas en un total de [math] \ binom {n -1} {k-1} [/ math] veces, cada partición contiene subconjuntos de tamaño [math] k [/ math], de modo que cada uno de los [math] \ binom {n} {k} [/ math] sea posible Se incluyen subconjuntos y ninguno se repite. Una explicación exhaustiva y legible y una prueba del teorema se encuentra en la Sección 2.4 de http://math.ucsb.edu/~padraic/uc…. Como se muestra en el enlace, el teorema de Baranyai proporciona una prueba inductiva constructiva al utilizar el teorema de corte mínimo de flujo máximo. Una implementación del código Python del algoritmo está en http://stackoverflow.com/a/25902….
Al ejecutar el código en el enlace StackOverflow para nuestro caso (baranyai (18, 3)), obtenemos las siguientes [matemáticas] \ binom {18-1} {3-1} = 136 [/ matemáticas] que cubren todas las [matemáticas] \ binom {18} {3} = 816 [/ math] de los subconjuntos [math] 3 [/ math].
[(0, 3, 11), (1, 10, 15), (2, 13, 16), (4, 7, 12), (5, 8, 17), (6, 9, 14)]
[(0, 10, 15), (1, 16, 17), (2, 4, 8), (3, 5, 7), (6, 12, 14), (9, 11, 13)]
[(0, 4, 17), (1, 8, 9), (2, 5, 12), (3, 6, 7), (10, 11, 14), (13, 15, 16)]
[(0, 4, 16), (1, 3, 15), (2, 7, 11), (5, 12, 17), (6, 8, 10), (9, 13, 14)]
[(0, 3, 12), (1, 10, 11), (2, 6, 7), (4, 5, 16), (8, 14, 15), (9, 13, 17)]
[(0, 4, 12), (1, 14, 15), (2, 6, 11), (3, 8, 17), (5, 9, 13), (7, 10, 16)]
[(0, 2, 8), (1, 4, 11), (3, 14, 16), (5, 6, 13), (7, 10, 15), (9, 12, 17)]
[(0, 5, 11), (1, 4, 8), (2, 3, 13), (6, 7, 17), (9, 10, 15), (12, 14, 16)]
[(0, 6, 16), (1, 13, 14), (2, 7, 17), (3, 4, 15), (5, 9, 10), (8, 11, 12)]
[(0, 8, 10), (1, 7, 15), (2, 12, 17), (3, 6, 14), (4, 9, 16), (5, 11, 13)]
[(0, 8, 14), (1, 9, 15), (2, 5, 6), (3, 7, 11), (4, 12, 17), (10, 13, 16)]
[(0, 13, 15), (1, 2, 9), (3, 4, 7), (5, 6, 8), (10, 14, 17), (11, 12, 16)]
[(0, 3, 13), (1, 4, 7), (2, 9, 15), (5, 11, 12), (6, 16, 17), (8, 10, 14)]
[(0, 7, 15), (1, 6, 17), (2, 12, 16), (3, 9, 13), (4, 8, 11), (5, 10, 14)]
[(0, 5, 17), (1, 6, 15), (2, 3, 16), (4, 12, 13), (7, 11, 14), (8, 9, 10)]
[(0, 11, 16), (1, 12, 17), (2, 6, 13), (3, 10, 15), (4, 7, 8), (5, 9, 14)]
[(0, 15, 16), (1, 2, 10), (3, 14, 17), (4, 5, 11), (6, 7, 12), (8, 9, 13)]
[(0, 1, 11), (2, 13, 14), (3, 4, 9), (5, 6, 12), (7, 16, 17), (8, 10, 15)]
[(0, 10, 17), (1, 8, 12), (2, 5, 15), (3, 6, 13), (4, 14, 16), (7, 9, 11)]
[(0, 1, 7), (2, 9, 12), (3, 8, 10), (4, 16, 17), (5, 13, 14), (6, 11, 15)]
[(0, 7, 17), (1, 6, 13), (2, 14, 15), (3, 5, 12), (4, 8, 9), (10, 11, 16)]
[(0, 11, 14), (1, 4, 16), (2, 6, 8), (3, 9, 15), (5, 12, 13), (7, 10, 17)]
[(0, 2, 7), (1, 5, 6), (3, 4, 10), (8, 9, 15), (11, 12, 14), (13, 16, 17)]
[(0, 8, 9), (1, 5, 14), (2, 4, 12), (3, 13, 16), (6, 10, 11), (7, 15, 17)]
[(0, 1, 17), (2, 8, 16), (3, 6, 9), (4, 11, 14), (5, 10, 13), (7, 12, 15)]
[(0, 5, 15), (1, 7, 13), (2, 9, 10), (3, 8, 14), (4, 11, 16), (6, 12, 17)]
[(0, 2, 5), (1, 6, 8), (3, 4, 11), (7, 9, 10), (12, 13, 17), (14, 15, 16)]
[(0, 2, 17), (1, 4, 10), (3, 7, 16), (5, 8, 12), (6, 11, 14), (9, 13, 15)]
[(0, 3, 5), (1, 6, 7), (2, 14, 16), (4, 8, 12), (9, 15, 17), (10, 11, 13)]
[(0, 4, 6), (1, 5, 10), (2, 3, 15), (7, 13, 16), (8, 9, 11), (12, 14, 17)]
[(0, 2, 13), (1, 7, 16), (3, 10, 11), (4, 5, 15), (6, 8, 12), (9, 14, 17)]
[(0, 5, 10), (1, 4, 15), (2, 12, 13), (3, 11, 17), (6, 8, 14), (7, 9, 16)]
[(0, 6, 8), (1, 5, 11), (2, 4, 13), (3, 7, 17), (9, 12, 16), (10, 14, 15)]
[(0, 6, 17), (1, 4, 5), (2, 3, 7), (8, 15, 16), (9, 11, 12), (10, 13, 14)]
[(0, 9, 15), (1, 10, 14), (2, 5, 13), (3, 12, 17), (4, 7, 16), (6, 8, 11)]
[(0, 12, 17), (1, 3, 10), (2, 9, 11), (4, 5, 14), (6, 13, 15), (7, 8, 16)]
[(0, 3, 10), (1, 9, 14), (2, 6, 16), (4, 11, 15), (5, 8, 13), (7, 12, 17)]
[(0, 2, 15), (1, 5, 16), (3, 6, 11), (4, 9, 10), (7, 14, 17), (8, 12, 13)]
[(0, 3, 8), (1, 14, 16), (2, 9, 17), (4, 6, 10), (5, 12, 15), (7, 11, 13)]
[(0, 5, 7), (1, 2, 17), (3, 4, 14), (6, 8, 16), (9, 10, 13), (11, 12, 15)]
[(0, 8, 12), (1, 15, 16), (2, 6, 9), (3, 13, 17), (4, 7, 14), (5, 10, 11)]
[(0, 3, 16), (1, 11, 13), (2, 7, 12), (4, 6, 17), (5, 8, 10), (9, 14, 15)]
[(0, 12, 13), (1, 9, 16), (2, 3, 14), (4, 7, 10), (5, 11, 15), (6, 8, 17)]
[(0, 6, 14), (1, 3, 7), (2, 10, 13), (4, 8, 16), (5, 9, 11), (12, 15, 17)]
[(0, 13, 14), (1, 11, 16), (2, 4, 10), (3, 9, 12), (5, 6, 17), (7, 8, 15)]
[(0, 5, 9), (1, 6, 10), (2, 11, 14), (3, 15, 17), (4, 13, 16), (7, 8, 12)]
[(0, 1, 3), (2, 4, 6), (5, 7, 8), (9, 10, 11), (12, 13, 15), (14, 16, 17)]
[(0, 6, 11), (1, 5, 17), (2, 4, 16), (3, 10, 14), (7, 9, 13), (8, 12, 15)]
[(0, 10, 13), (1, 3, 9), (2, 4, 11), (5, 7, 14), (6, 15, 16), (8, 12, 17)]
[(0, 9, 13), (1, 15, 17), (2, 10, 11), (3, 5, 6), (4, 8, 14), (7, 12, 16)]
[(0, 4, 11), (1, 5, 12), (2, 8, 10), (3, 6, 15), (7, 13, 14), (9, 16, 17)]
[(0, 1, 14), (2, 10, 12), (3, 9, 11), (4, 6, 7), (5, 13, 16), (8, 15, 17)]
[(0, 6, 15), (1, 10, 16), (2, 3, 11), (4, 9, 13), (5, 12, 14), (7, 8, 17)]
[(0, 2, 16), (1, 7, 9), (3, 5, 8), (4, 6, 11), (10, 12, 15), (13, 14, 17)]
[(0, 8, 16), (1, 7, 10), (2, 6, 15), (3, 12, 14), (4, 9, 11), (5, 13, 17)]
[(0, 5, 13), (1, 11, 14), (2, 7, 16), (3, 6, 12), (4, 8, 15), (9, 10, 17)]
[(0, 1, 15), (2, 8, 12), (3, 9, 16), (4, 10, 14), (5, 7, 13), (6, 11, 17)]
[(0, 2, 10), (1, 3, 4), (5, 6, 7), (8, 9, 16), (11, 12, 13), (14, 15, 17)]
[(0, 9, 12), (1, 8, 13), (2, 11, 15), (3, 16, 17), (4, 6, 14), (5, 7, 10)]
[(0, 11, 15), (1, 5, 8), (2, 13, 17), (3, 4, 12), (6, 7, 14), (9, 10, 16)]
[(0, 12, 14), (1, 6, 9), (2, 4, 17), (3, 5, 10), (7, 11, 16), (8, 13, 15)]
[(0, 11, 13), (1, 12, 16), (2, 7, 9), (3, 10, 17), (4, 5, 8), (6, 14, 15)]
[(0, 3, 17), (1, 12, 14), (2, 7, 13), (4, 8, 10), (5, 9, 15), (6, 11, 16)]
[(0, 10, 14), (1, 2, 3), (4, 5, 6), (7, 8, 11), (9, 12, 13), (15, 16, 17)]
[(0, 6, 13), (1, 4, 17), (2, 5, 7), (3, 15, 16), (8, 9, 14), (10, 11, 12)]
[(0, 6, 9), (1, 3, 17), (2, 4, 5), (7, 12, 13), (8, 14, 16), (10, 11, 15)]
[(0, 16, 17), (1, 6, 11), (2, 12, 14), (3, 13, 15), (4, 5, 10), (7, 8, 9)]
[(0, 6, 7), (1, 9, 11), (2, 3, 10), (4, 15, 17), (5, 12, 16), (8, 13, 14)]
[(0, 7, 10), (1, 2, 13), (3, 12, 15), (4, 8, 17), (5, 6, 11), (9, 14, 16)]
[(0, 1, 8), (2, 6, 14), (3, 11, 15), (4, 10, 17), (5, 7, 12), (9, 13, 16)]
[(0, 14, 15), (1, 2, 8), (3, 4, 16), (5, 6, 9), (7, 10, 12), (11, 13, 17)]
[(0, 3, 7), (1, 13, 16), (2, 5, 17), (4, 6, 12), (8, 11, 15), (9, 10, 14)]
[(0, 2, 11), (1, 9, 10), (3, 8, 15), (4, 7, 17), (5, 6, 16), (12, 13, 14)]
[(0, 2, 14), (1, 7, 11), (3, 8, 13), (4, 5, 17), (6, 10, 12), (9, 15, 16)]
[(0, 2, 4), (1, 3, 6), (5, 7, 9), (8, 11, 16), (10, 13, 17), (12, 14, 15)]
[(0, 10, 11), (1, 8, 15), (2, 3, 5), (4, 13, 14), (6, 12, 16), (7, 9, 17)]
[(0, 3, 6), (1, 2, 7), (4, 5, 9), (8, 10, 12), (11, 15, 17), (13, 14, 16)]
[(0, 5, 6), (1, 13, 15), (2, 4, 9), (3, 8, 12), (7, 10, 14), (11, 16, 17)]
[(0, 9, 14), (1, 7, 12), (2, 5, 8), (3, 10, 16), (4, 11, 13), (6, 15, 17)]
[(0, 7, 9), (1, 11, 12), (2, 8, 15), (3, 4, 13), (5, 14, 16), (6, 10, 17)]
[(0, 4, 10), (1, 11, 17), (2, 15, 16), (3, 7, 13), (5, 6, 14), (8, 9, 12)]
[(0, 1, 10), (2, 9, 16), (3, 4, 17), (5, 8, 14), (6, 12, 13), (7, 11, 15)]
[(0, 3, 15), (1, 2, 4), (5, 9, 17), (6, 13, 16), (7, 10, 11), (8, 12, 14)]
[(0, 5, 16), (1, 7, 17), (2, 11, 12), (3, 8, 9), (4, 10, 15), (6, 13, 14)]
[(0, 4, 13), (1, 3, 16), (2, 6, 17), (5, 7, 15), (8, 11, 14), (9, 10, 12)]
[(0, 2, 12), (1, 3, 8), (4, 5, 7), (6, 14, 16), (9, 11, 17), (10, 13, 15)]
[(0, 10, 12), (1, 2, 5), (3, 13, 14), (4, 15, 16), (6, 8, 9), (7, 11, 17)]
[(0, 4, 14), (1, 8, 11), (2, 16, 17), (3, 10, 12), (5, 13, 15), (6, 7, 9)]
[(0, 11, 17), (1, 8, 10), (2, 5, 9), (3, 12, 13), (4, 6, 16), (7, 14, 15)]
[(0, 2, 6), (1, 4, 12), (3, 5, 9), (7, 8, 13), (10, 15, 16), (11, 14, 17)]
[(0, 8, 15), (1, 9, 17), (2, 3, 12), (4, 7, 13), (5, 11, 14), (6, 10, 16)]
[(0, 5, 14), (1, 11, 15), (2, 8, 17), (3, 7, 12), (4, 10, 13), (6, 9, 16)]
[(0, 1, 6), (2, 14, 17), (3, 4, 5), (7, 10, 13), (8, 12, 16), (9, 11, 15)]
[(0, 1, 9), (2, 11, 17), (3, 10, 13), (4, 6, 8), (5, 15, 16), (7, 12, 14)]
[(0, 13, 17), (1, 4, 14), (2, 7, 15), (3, 8, 16), (5, 10, 12), (6, 9, 11)]
[(0, 8, 13), (1, 2, 16), (3, 9, 10), (4, 14, 15), (5, 7, 17), (6, 11, 12)]
[(0, 9, 17), (1, 8, 14), (2, 10, 16), (3, 5, 13), (4, 6, 15), (7, 11, 12)]
[(0, 13, 16), (1, 10, 12), (2, 5, 11), (3, 4, 8), (6, 14, 17), (7, 9, 15)]
[(0, 1, 4), (2, 3, 9), (5, 6, 15), (7, 8, 14), (10, 11, 17), (12, 13, 16)]
[(0, 14, 17), (1, 9, 13), (2, 3, 6), (4, 10, 12), (5, 8, 11), (7, 15, 16)]
[(0, 11, 12), (1, 10, 17), (2, 13, 15), (3, 6, 8), (4, 9, 14), (5, 7, 16)]
[(0, 12, 16), (1, 5, 15), (2, 9, 13), (3, 6, 10), (4, 7, 11), (8, 14, 17)]
[(0, 2, 3), (1, 4, 9), (5, 8, 16), (6, 7, 11), (10, 12, 14), (13, 15, 17)]
[(0, 7, 8), (1, 2, 15), (3, 11, 14), (4, 10, 16), (5, 9, 12), (6, 13, 17)]
[(0, 9, 10), (1, 7, 14), (2, 6, 12), (3, 11, 16), (4, 8, 13), (5, 15, 17)]
[(0, 3, 4), (1, 2, 12), (5, 8, 9), (6, 10, 14), (7, 13, 17), (11, 15, 16)]
[(0, 3, 14), (1, 5, 7), (2, 4, 15), (6, 8, 13), (9, 11, 16), (10, 12, 17)]
[(0, 8, 11), (1, 12, 13), (2, 4, 14), (3, 7, 15), (5, 16, 17), (6, 9, 10)]
[(0, 7, 12), (1, 2, 6), (3, 5, 17), (4, 9, 15), (8, 10, 16), (11, 13, 14)]
[(0, 4, 5), (1, 3, 14), (2, 12, 15), (6, 7, 10), (8, 9, 17), (11, 13, 16)]
[(0, 15, 17), (1, 6, 14), (2, 8, 13), (3, 7, 10), (4, 11, 12), (5, 9, 16)]
[(0, 7, 14), (1, 8, 17), (2, 5, 10), (3, 11, 13), (4, 6, 9), (12, 15, 16)]
[(0, 9, 16), (1, 5, 13), (2, 6, 10), (3, 7, 14), (4, 12, 15), (8, 11, 17)]
[(0, 8, 17), (1, 3, 13), (2, 7, 14), (4, 9, 12), (5, 11, 16), (6, 10, 15)]
[(0, 1, 2), (3, 5, 14), (4, 10, 11), (6, 7, 16), (8, 13, 17), (9, 12, 15)]
[(0, 7, 11), (1, 10, 13), (2, 8, 9), (3, 5, 16), (4, 14, 17), (6, 12, 15)]
[(0, 7, 16), (1, 3, 12), (2, 8, 14), (4, 9, 17), (5, 10, 15), (6, 11, 13)]
[(0, 4, 15), (1, 14, 17), (2, 7, 8), (3, 11, 12), (5, 10, 16), (6, 9, 13)]
[(0, 12, 15), (1, 6, 16), (2, 9, 14), (3, 5, 11), (4, 13, 17), (7, 8, 10)]
[(0, 1, 13), (2, 10, 14), (3, 12, 16), (4, 7, 9), (5, 11, 17), (6, 8, 15)]
[(0, 5, 8), (1, 3, 11), (2, 15, 17), (4, 12, 16), (6, 10, 13), (7, 9, 14)]
[(0, 6, 10), (1, 8, 16), (2, 5, 14), (3, 7, 9), (4, 13, 15), (11, 12, 17)]
[(0, 9, 11), (1, 12, 15), (2, 7, 10), (3, 4, 6), (5, 14, 17), (8, 13, 16)]
[(0, 7, 13), (1, 4, 6), (2, 3, 17), (5, 8, 15), (9, 11, 14), (10, 12, 16)]
[(0, 3, 9), (1, 2, 14), (4, 5, 12), (6, 7, 8), (10, 16, 17), (11, 13, 15)]
[(0, 1, 12), (2, 4, 7), (3, 5, 15), (6, 9, 17), (8, 11, 13), (10, 14, 16)]
[(0, 1, 5), (2, 3, 8), (4, 6, 13), (7, 9, 12), (10, 15, 17), (11, 14, 16)]
[(0, 14, 16), (1, 3, 5), (2, 11, 13), (4, 7, 15), (6, 9, 12), (8, 10, 17)]
[(0, 4, 7), (1, 6, 12), (2, 5, 16), (3, 9, 17), (8, 10, 13), (11, 14, 15)]
[(0, 6, 12), (1, 4, 13), (2, 10, 15), (3, 9, 14), (5, 7, 11), (8, 16, 17)]
[(0, 5, 12), (1, 13, 17), (2, 3, 4), (6, 9, 15), (7, 14, 16), (8, 10, 11)]
[(0, 1, 16), (2, 10, 17), (3, 8, 11), (4, 5, 13), (6, 7, 15), (9, 12, 14)]
[(0, 4, 8), (1, 9, 12), (2, 11, 16), (3, 14, 15), (5, 10, 17), (6, 7, 13)]
[(0, 4, 9), (1, 2, 11), (3, 7, 8), (5, 6, 10), (12, 16, 17), (13, 14, 15)]
[(0, 2, 9), (1, 7, 8), (3, 6, 16), (4, 11, 17), (5, 14, 15), (10, 12, 13)]
[(0, 10, 16), (1, 5, 9), (2, 8, 11), (3, 6, 17), (4, 12, 14), (7, 13, 15)]
