¿Cuál fue el problema matemático que el personaje de Matt Damon resolvió como conserje en una escena temprana en Good Will Hunting?

Problema:

1. Encuentre la matriz de adyacencia A del gráfico anterior G.
2. Encuentre la matriz que da el número de 3 pasos en G.
3. Encuentre la función generadora de caminatas desde el punto i hasta j.
4. Encuentre la función generadora para caminatas de los puntos 1 a 3.

La matriz de adyacencia L codifica el gráfico. La entrada Lij es igual a k si hay k conexiones entre el nodo i y j. De lo contrario, la entrada es cero. El problema 2 pide encontrar la matriz que codifica todas las rutas posibles de longitud 3.

• Si la correlación (A, B) es +0.8, ¿se puede concluir que un rendimiento positivo del stock A va acompañado de un rendimiento positivo del stock B el 80% del tiempo?
• ¿Cuántos cuadrados hay en un tablero de ajedrez 8 × 8?
• ¿Realmente puede haber algo como X dentro de otra X o algo similar?
• Cómo imaginar o visualizar un producto de funciones
• Cómo demostrar que el valor mínimo de | za | + | zb | es | ab |

Función generadora. A un gráfico se puede asignar para un par de nodos series i, ja , donde an (ij) es el número de caminatas de i a j con n pasos. El problema 3) pide una fórmula para f (z) y en el problema 4) una expresión explícita en el caso i = 1, j = 3.

Solución:

1. La matriz de adyacencia L es

2. [L ^ 2] ij es, por definición del producto matricial, la suma L-i1 L-1j + L-i2 L-2j +… + L-en L-nj. Cada término L-i1 L-1j no es 0 si y solo si hay al menos un camino de longitud 2 que va de i a j pasando por k. Por lo tanto, [L ^ 2] ij es el número de rutas de longitud 2 que van del nodo i a j. Del mismo modo, [L ^ n] ij es el número de caminos de longitud n que van de i a j. La respuesta es

3. El para la suma de una serie geométrica vale también para matrices: . La regla de Cramer para el inverso de una matriz es A ^ -1 = det (Adj (A) ij) / det (A) conduce a det (Adj (1-z L) ij) / det (1-z L) que puede también se escribirá como det (Adj (Lz) ij) / det (Lz).

4. Especialmente, cuando i = 1 y j = 3, obtenemos det (Adj (A) 13 = 2 z ^ 2 + 2 z ^ 3 y det (Lz) = 1-7 z ^ 2 – 2 z ^ 3 + 4 z ^ 4. El resultado se puede escribir como (2 z ^ 3 + 2z ^ 3) / (1-7 z ^ 2- 2 z ^ 3 + 4 z ^ 4).

Todo aquí: http://www.math.harvard.edu/arch…