Combinatoria: ¿Cuál es un método eficiente y sistemático para organizar 9 letras (A, B, C, D, E, F, G, H, I) en grupos de tres (ABC – AEF – IBD -DAC- …) en tal de manera que ninguna carta en particular comparte un grupo con otra letra en particular más de una vez?

Esta es una respuesta más general en la que no estamos restringidos solo a alfabetos [matemáticos] 9 [/ matemáticos], sino a alfabetos [matemáticos] 3 ^ {n} [/ matemáticos].

Primero déjame establecer un teorema:

Teorema:
Sea [math] n [/ math] el número de alfabetos que nos interesan. Si [math] n [/ math] es una potencia de 3, entonces podemos construir [math] \ frac {3 ^ {n} ( 3 ^ {n} +1)} {6} [/ math] se triplica como máximo. (Tenga en cuenta que su pregunta tiene solo 9 letras, por lo tanto, cae en este caso especial)

Prueba:
Claramente, este es un límite superior ya que tenemos exactamente [matemática] \ frac {3 ^ {n} (3 ^ {n} +1)} {2} [/ matemática] pares y, por lo tanto, podemos tener como máximo [matemática] \ frac {3 ^ {n} (3 ^ {n} +1)} {6} [/ math] se triplica ya que cada triple contiene [math] 3 [/ math] pares.

Un hecho aún más sorprendente (al menos para mí) es que siempre podemos encontrar exactamente [matemáticas] \ frac {3 ^ {n} (3 ^ {n} +1)} {6} [/ matemáticas] se triplica.

Daré un algoritmo para construir estos triples.

Consideremos la posibilidad de construir estos triples colocando nuestros trillizos en conjuntos y no combinando trillizos del mismo conjunto al construir nuevos trillizos. Tenga en cuenta que simplemente podemos considerar la mejor manera de construir estos triples combinando tres triples de diferentes conjuntos.

Como [math] n [/ math] es divisible por 3, sabemos que debe haber al menos [math] \ frac {n} {3} [/ math] tales triples. Pero cada uno de estos triples pertenece a diferentes conjuntos y no se pueden emparejar dos miembros del mismo conjunto. Por lo tanto, estos conjuntos [matemáticos] \ frac {n} {3} [/ matemáticos] deben emparejarse de manera óptima también para construir un emparejamiento óptimo. Por ‘par’ me refiero a elegir 3 juegos y construir 9 nuevos triples. Por ejemplo:
Sean los tres triples (a, b, c), (d, e, f), (g, h, i), entonces nuestros 9 triples nuevos son (a, d, g) (a, e, h) (a , f, i) (b, d, h) (b, e, i) (b, f, g) (c, d, i) (c, e, g) (c, f, h)
(Ver los comentarios de Raziman TV en su respuesta)

Ahora aquí hay un algoritmo para construir los conjuntos .
Representemos las letras por números [matemáticas] 1,2,3, …, 3 ^ {n} [/ matemáticas].

Lo implementé a continuación en Ruby:

$set_count = 1 def print_tripples(a,b,c) #zero indexing puts "set #{$set_count} : (#{a},#{b},#{c})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a},#{b+1},#{c+1})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a},#{b+2},#{c+2})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a+1},#{b},#{c+1})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a+1},#{b+1},#{c+2})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a+1},#{b+2},#{c})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a+2},#{b},#{c+2})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a+2},#{b+1},#{c})" $set_count = $set_count +1 puts "set #{$set_count} : (#{a+2},#{b+2},#{c+1})" $set_count = $set_count +1 end def print_3_sets(l1,l2,l3,w,max) #Assume you have more than 3 letters #l1 = low 1 #l2 = low 2 #l3 = low 3 #w = width if l1<l2 and l2<l3 and l31 print_3_sets(l1,l2,l3,k,max) print_3_sets(l1,l2+k,l3+k,k,max) print_3_sets(l1,l2+2*k,l3+2*k,k,max) print_3_sets(l1+k,l2,l3+k,k,max) print_3_sets(l1+k,l2+k,l3+2*k,k,max) print_3_sets(l1+k,l2+2*k,l3,k,max) print_3_sets(l1+2*k,l2,l3+2*k,k,max) print_3_sets(l1+2*k,l2+k,l3,k,max) print_3_sets(l1+2*k,l2+2*k,l3+k,k,max) end end end end n=6 #first list the obvious first sets i=1 while i<3**n puts "set #{$set_count} : (#{i},#{i+1},#{i+2})" $set_count = $set_count +1 i = i+3 end num_of_letters = 3**n #assuming it's always a power of 3 greater than 3 #print_3_sets(1,1+num_of_letters/3,1+2*num_of_letters/3,num_of_letters,num_of_letters) diff = 9 t = 2 while diff <= num_of_letters j=1 while j<num_of_letters print_3_sets(j,j+diff/3,j+2*diff/3,diff,j+diff-1) j=j+diff end t = t+1 diff = 3**t end 

La forma en que funciona es mediante la partición recursiva de los conjuntos [math] \ frac {n} {3} [/ math] de manera óptima. Hay [matemáticas] 9 [/ matemáticas] particiones en cada paso. De ahí las llamadas recursivas [math] 9 [/ math]. (Tenga en cuenta que, en general, la cantidad de triples es [matemática] O (n ^ {2}) [/ matemática]).

Para dar más explicaciones sobre cómo funciona. Supongamos que hemos encontrado una ‘mejor’ forma de particionar las letras [math] 3 ^ {n} [/ math]. Entonces debemos tener al menos [math] 3 ^ {n-1} [/ math] tal conjunto. considere el momento en el que simplemente elegimos estas [matemáticas] 3 ^ {n-1} [/ matemáticas] letras. Solo los tenemos y tenemos que encontrar una manera de conectar las letras para formar más trillizos de la manera óptima.

Resulta que si dividimos estos subconjuntos [math] 3 ^ {n-1} [/ math] en grupos [math] 3 [/ math] y dividimos estos grupos [math] 3 [/ math] de manera óptima y luego conectamos el miembros de forma óptima también, obtenemos exactamente [math] \ frac {3 ^ {n} (3 ^ {n} +1)} {6} [/ math] trillizos! Por “conectar” me refiero simplemente a elegir los conjuntos.

Así es exactamente como funciona el algoritmo anterior. 🙂
Si observa el código el tiempo suficiente, obtendrá la idea.
Puede ser útil pensar en los alfabetos como nodos en un gráfico y las conexiones como bordes. es decir, si elige tres vértices, forma un triángulo entre los vértices y ningún otro triángulo puede compartir los bordes de este triángulo.

Solo para demostrar que funciona, aquí hay una partición óptima cuando tenemos [matemáticas] 27 [/ matemáticas] en el alfabeto cada una etiquetada [matemáticas] 1,2,3,…, 27 [/ matemáticas]. Puede confirmar que no hay superposición de pares:

  conjunto 1: (1,2,3)
 conjunto 2: (4,5,6)
 conjunto 3: (7,8,9)
 conjunto 4: (10,11,12)
 conjunto 5: (13,14,15)
 conjunto 6: (16,17,18)
 conjunto 7: (19,20,21)
 conjunto 8: (22,23,24)
 conjunto 9: (25,26,27)
 conjunto 10: (1,4,7)
 conjunto 11: (1,5,8)
 conjunto 12: (1,6,9)
 set 13: (2,4,8)
 conjunto 14: (2,5,9)
 set 15: (2,6,7)
 conjunto 16: (3,4,9)
 conjunto 17: (3,5,7)
 conjunto 18: (3,6,8)
 conjunto 19: (10,13,16)
 conjunto 20: (10,14,17)
 conjunto 21: (10,15,18)
 conjunto 22: (11,13,17)
 conjunto 23: (11,14,18)
 conjunto 24: (11,15,16)
 conjunto 25: (12,13,18)
 conjunto 26: (12,14,16)
 conjunto 27: (12,15,17)
 conjunto 28: (19,22,25)
 conjunto 29: (19,23,26)
 conjunto 30: (19,24,27)
 conjunto 31: (20,22,26)
 conjunto 32: (20,23,27)
 conjunto 33: (20,24,25)
 conjunto 34: (21,22,27)
 conjunto 35: (21,23,25)
 conjunto 36: (21,24,26)
 conjunto 37: (1,10,19)
 conjunto 38: (1,11,20)
 conjunto 39: (1,12,21)
 conjunto 40: (2,10,20)
 conjunto 41: (2,11,21)
 conjunto 42: (2,12,19)
 conjunto 43: (3,10,21)
 set 44: (3,11,19)
 conjunto 45: (3,12,20)
 conjunto 46: (1,13,22)
 conjunto 47: (1,14,23)
 conjunto 48: (1,15,24)
 conjunto 49: (2,13,23)
 conjunto 50: (2,14,24)
 conjunto 51: (2,15,22)
 conjunto 52: (3,13,24)
 conjunto 53: (3,14,22)
 conjunto 54: (3,15,23)
 conjunto 55: (1,16,25)
 conjunto 56: (1,17,26)
 conjunto 57: (1,18,27)
 conjunto 58: (2,16,26)
 conjunto 59: (2,17,27)
 conjunto 60: (2,18,25)
 set 61: (3,16,27)
 conjunto 62: (3,17,25)
 conjunto 63: (3,18,26)
 conjunto 64: (4,10,22)
 conjunto 65: (4,11,23)
 conjunto 66: (4,12,24)
 conjunto 67: (5,10,23)
 conjunto 68: (5,11,24)
 conjunto 69: (5,12,22)
 conjunto 70: (6,10,24)
 conjunto 71: (6,11,22)
 conjunto 72: (6,12,23)
 conjunto 73: (4,13,25)
 conjunto 74: (4,14,26)
 conjunto 75: (4,15,27)
 conjunto 76: (5,13,26)
 conjunto 77: (5,14,27)
 conjunto 78: (5,15,25)
 conjunto 79: (6,13,27)
 conjunto 80: (6,14,25)
 conjunto 81: (6,15,26)
 conjunto 82: (4,16,19)
 set 83: (4,17,20)
 set 84: (4,18,21)
 conjunto 85: (5,16,20)
 conjunto 86: (5,17,21)
 conjunto 87: (5,18,19)
 conjunto 88: (6,16,21)
 conjunto 89: (6,17,19)
 conjunto 90: (6,18,20)
 conjunto 91: (7,10,25)
 conjunto 92: (7,11,26)
 conjunto 93: (7,12,27)
 conjunto 94: (8,10,26)
 conjunto 95: (8,11,27)
 set 96: (8,12,25)
 conjunto 97: (9,10,27)
 conjunto 98: (9,11,25)
 conjunto 99: (9,12,26)
 set 100: (7,13,19)
 conjunto 101: (7,14,20)
 conjunto 102: (7,15,21)
 set 103: (8,13,20)
 conjunto 104: (8,14,21)
 conjunto 105: (8,15,19)
 conjunto 106: (9,13,21)
 conjunto 107: (9,14,19)
 set 108: (9,15,20)
 set 109: (7,16,22)
 conjunto 110: (7,17,23)
 conjunto 111: (7,18,24)
 conjunto 112: (8,16,23)
 set 113: (8,17,24)
 conjunto 114: (8,18,22)
 set 115: (9,16,24)
 conjunto 116: (9,17,22)
 conjunto 117: (9,18,23)

Esto se debe a la parte de la combinatoria llamada teoría del diseño que se utiliza para diseñar experimentos eficientes, entre otras cosas. Daré una construcción específica y luego haré comentarios más generales.

Deje que las letras correspondan a pares ordenados de elementos de [math] \ lbrace 0,1,2 \ rbrace: [/ math] [math] A = (0,0), B = (0,1), C = (0 , 2), D = (1,0),… [/ matemáticas]

Deje que los grupos sean los triples cuyas sumas tienen coordenadas divisibles por 3. Por ejemplo, [matemáticas] (0,0) + (0,1) + (0,2) = (0,3) [/ matemáticas] para que formen un triple Esto proporciona un conjunto de 12 triples para que cualquiera de los dos esté contenido precisamente en un triple.

Otra forma de ver la misma construcción es que los triples son las líneas sobre los enteros mod 3, soluciones a [matemática] Ax + By \ equiv C \ mod 3 [/ matemática] para algunos triples de enteros [matemática] (A, B, C) [/ matemáticas] donde A y B no pueden ser divisibles por 3. Dos puntos determinan una línea única. Hay 4 posibles pendientes de líneas: Vertical, 0, 1 y 2. Para cada pendiente, hay 3 líneas disjuntas con esa pendiente. Esto se llama el plano afín sobre el campo con 3 elementos.

En el popular juego de cartas SET, hay 81 cartas con 4 características: color, número, forma y textura. Cada característica tiene una de 3 posibilidades, por ejemplo, las tarjetas pueden ser rojas, moradas o verdes.


En el juego, su tarea es identificar Conjuntos, triples de cartas para que en cada característica, las 3 cartas sean iguales o las cartas sean todas diferentes. Esto es equivalente a encontrar líneas en 4 espacios afines sobre el campo con 3 elementos. Si arregla dos características, digamos tarjetas rojas con óvalos, entonces hay 9 tarjetas con esa restricción. Hay 12 Conjuntos posibles entre estas 9 cartas, y forman un plano afín, un sistema de triples idéntico a la construcción anterior.

En términos más generales, si hay n puntos, puede esperar encontrar un sistema de [matemática] {n \ elegir 2} / 3 [/ matemática] triples para que cada par de puntos distintos esté contenido en un triple único. Esto se llama un sistema triple Steiner, y siempre existen cuando n es 1 o 3 mod 6, y no son demasiado difíciles de construir. De lo contrario, las restricciones de integralidad simple lo prohíben. Cuando n es 3 mod 6, también puede pedir que los triples se puedan dividir en clases de paralelismo como las 4 pendientes. Estos se llaman resolubles y existen sistemas triples con estas restricciones. El caso de n = 15 se conoce como el problema de la colegiala de Kirkman, y creo que Dudeney preguntó sobre el caso de n = 9 en uno de sus acertijos.

En términos mucho más generales, puede solicitar conjuntos de mayor tamaño para que cada t-tupla esté cubierta la misma cantidad de veces. Como dice Justin Rising, estos se llaman diseños de bloques.

Existe un enfoque bien conocido (cf: coeficientes multinomiales – matemática discreta) para agrupar los elementos de un conjunto en subconjuntos disjuntos, que estoy aplicando aquí para este problema con diferentes condiciones.
[Bricolaje: utilice el enfoque para resolver el problema con sus condiciones y verifique su eficacia relativa]

Objetivo:
Grupo 3 (G, G1, G2, G3): – distribuya los 9 elementos de G en subgrupos disjuntos G1, G2 y G3, de modo que G1, G2 y G3 contengan 2,3 y 4 elementos, por ejemplo
grupo3 ([a, b, c, d, e, f, g, h, i], G1, G2, G3) a-> G1 = [a, b], G2 = [c, d, e], G3 = [f, g, h, i]

Dado que [a, b] es indistinguible de [b, a]. [(A, b), (c, d)] es distinguible de [(c, d), (a, b)].

Acercarse a, aproximarse:
grupo3 (G, G1, G2, G3): –
seleccioneN (2, G, G1),
restar (G, G1, R1),
seleccioneN (3, R1, G2),
restar (R1, G2, R2),
seleccioneN (4, R2, G3),
restar (R2, G3, []).
seleccioneN (N, L, S): –
seleccione N elementos de la lista L y colóquelos en el conjunto S. Mediante el seguimiento inverso, devuelva todas las selecciones posibles, pero evite las permutaciones; es decir, después de generar S = [a, b, c] no devuelve% S = [b, a, c], etc.

selectN (0, _, []): – !.
selectN (N, L, [X | S]): –
N> 0, el (X, L, R),
N1 es N-1,
seleccione N (N1, R, S).
el (X, [X | L], L). el (X, [_ | L], R): –
el (X, L, R).
restar / 3 está predefinido

12)

El principio del casillero nos ayuda aquí. 9C2 = 36 pares de letras se pueden hacer de 9 letras. Cada triplete de letras nos da 3 pares de letras (por ejemplo, ABC da AB, AC y BC). Si tenemos 13 trillizos de letras, habría 39 pares de letras en total, por lo que algunos pares de letras deben repetirse. Por lo tanto, 12 es un límite superior en la respuesta.

Así que tratemos de hacer 12 trillizos. Es fácil encontrar uno de estos conjuntos:
{ABC, DEF, GHI, ADG, AEH, AFI, BDH, BEI, BFG, CDI, CEG, CFH}

Así 12 es la respuesta.

Este es un ejemplo de lo que se conoce como diseño de bloques. En particular, es un diseño de bloque incompleto equilibrado con [matemática] v = 9 [/ matemática], [matemática] k = 3 [/ matemática] y [matemática] \ lambda = 1 [/ matemática]. No estoy familiarizado con los algoritmos para generar estos diseños, pero es un problema bastante estándar, por lo que debería haber algo por ahí.

More Interesting

En una pirámide numérica, ¿hay alguna forma de calcular el número total de diferentes números superiores dependiendo de cuántos números iniciales hay en la fila inferior de la pirámide?

¿Cómo puedo entender las anotaciones asintóticas?

¿Cómo encuentro el camino más corto entre dos puntos en la superficie de un objeto tridimensional?

¿Hay números irracionales que tienen una distribución no uniforme de dígitos cuando se expanden en la base n, donde n puede ser cualquier número natural, aparte de aquellos construidos artificialmente como la constante de Liouville?

¿Existe un patrón que le permita saber cuántos dígitos tendrá un producto de dos números, sin las matemáticas?

¿Cómo se factorizan [matemáticas] {\ nu ^ 3} – \ nu – 1 [/ matemáticas]?

“Dados los N enteros, siempre podemos encontrar dos enteros distintos cuya diferencia de cuadrados es un múltiplo de 1000”. ¿Cuál es el valor entero más pequeño de N que haría que la afirmación sea verdadera?

Dada una simple regresión lineal E (y) = bx1 + c + error, con solo una variable independiente, dos parámetros desconocidos y un rango de posibles observaciones para x1 = [0,100], ¿cómo podría llegar a un diseño secuencial bayesiano óptimo que minimiza la incertidumbre de mis estimaciones de parámetros en cada paso?

¿Cómo puedo demostrar que el algoritmo Pagerank es correcto y funciona?

Dado un número N <10 ^ 100, ¿cuántos números cuyos dígitos son una permutación de dígitos en N que son divisibles por 11? Gracias por adelantado.