¿De cuántas maneras puede una persona visitar 3 ciudades, cada ciudad exactamente 4 veces, de modo que comience y termine con una ciudad diferente?

Answer 1

804. (o 268 veces 3)

Al principio llegué a ese número haciendo una primera búsqueda profunda a través de posibles planes de viaje usando una computadora. Entonces pensé que el número de ciudades puede ser lo suficientemente pequeño como para que la tarea no sea tediosa cuando se realiza manualmente.

Cada posible plan de viaje puede representarse con una palabra de 12 letras usando las letras a, b, c. Entonces, una forma podría ser “abacabacbcbc”. Por lo tanto, estamos tratando de encontrar todas esas cadenas que tienen 4 de cada letra y no letras dobles y la primera y la última letra son diferentes. Supongamos que comenzamos en la ciudad ‘a’ (luego multiplicaremos la respuesta por 3 para tener la posibilidad de comenzar en cualquier lugar). Ahora podemos dividir cualquier cadena en cuatro espacios separados por ‘a’. La cadena anterior se parece a “a * a * a * a *****” con los espacios en blanco rellenados por “b”, “c”, “b” y “cbcbc” respectivamente. Cada espacio se llena con una serie alterna de b y c.

Las brechas juntas tendrán un total de 8 letras. Hay cinco formas de dividir 8 en 4 enteros positivos que son:

[matemáticas] 8 = 1 + 1 + 1 + 5 = 1 + 1 + 2 + 4 = 1 + 1 + 3 + 3 = 1 + 2 + 2 + 3 = 2 + 2 + 2 + 2 [/ matemáticas]

Ahora la partición 1 + 1 + 1 + 5 tiene 4 arreglos posibles dependiendo de dónde venga la brecha de tamaño 5. El espacio de 5 se puede llenar de 2 maneras: bcbcb o cbcbc. Luego, los otros 3 huecos se pueden llenar de 3 maneras. Esto nos da [matemática] 2 \ veces 3 = 6 [/ matemática] formas totales de llenar los vacíos. Por lo tanto, hay un total de 24 formas en que se puede llenar la partición (1, 1, 1, 5) de huecos.

De manera similar, se puede encontrar que la partición (1, 1, 2, 4) tiene 12 formas de organizar los espacios y cada disposición tiene 8 formas de llenar esos espacios con b, c. Una vez que hayamos terminado con las otras 3 formas de particiones también, obtenemos un total de 268 cadenas que comienzan con ‘a’. (¡Ah, respuestas del hombre y la máquina! Algo debe estar bien: D)

Apéndices

def deli (sofar, a, b, c):
si len (sofar) == 12:
return int (sofar [0]! = sofar [-1])
cuenta = 0
if sofar [-1]! = ‘a’ y a <4: count + = deli (sofar + 'a', a + 1, b, c)
if sofar [-1]! = ‘b’ yb <4: count + = deli (sofar + 'b', a, b + 1, c)
if sofar [-1]! = ‘c’ y c <4: count + = deli (sofar + 'c', a, b, c + 1)
cuenta de retorno

>>> deli (“a”, 1, 0, 0)
268

Partición: Arreglos x Rellenos de espacios = Total
1 1 1 5: 4 x 6 = 24
1 1 2 4: 12 x 8 = 96
1 1 3 3: 6 x 6 = 36
1 2 2 3: 12 x 8 = 96
2 2 2 2: 1 x 16 = 16
——————————————–
Gran total 268