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.
- ¿Qué tan efectivo es resolver un problema al día?
- ¿Qué significan los números primos muy grandes?
- Dada una matriz de tamaño m * n, ¿cómo ubica a k estudiantes de tal manera que se minimice la trampa en un examen?
- Dada una secuencia de + ve números, ¿encuentra las diferentes combinaciones de elementos cuya suma es mayor que la mitad de la suma total de la secuencia?
- ¿Cuántas pelotas de golf puedes meter en una tubería?
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)