Me preguntaba ¿cuántas combinaciones diferentes posibles hay para el desbloqueo de un teléfono Android. Con el fin de hacer esto, usted tiene que elegir un camino a partir de una gráfica:
La gráfica es no regular: los nodos de las esquinas están vinculados a los 5 nodos, los nodos a los lados están vinculados a 7 nodos y el nodo central está conectado a todos los otros.
El desbloqueo de los trazados pueden tener cualquier longitud entre 3 y 9. Hay una forma sencilla de contar las posibilidades?
Dos de las otras respuestas, incluyendo la aceptación de uno, el uso de la matriz de competencias que se equivoca de nuevo, porque esto incluye caminos que permiten pasar más de una vez en el mismo nodo. La tercera respuesta da una fórmula que carecen de una prueba de ningún tipo (hemos utilizado para tener en matemáticas cuando yo era joven), no entiendo por qué está mal, y por qué debe ser correcto en el primer lugar, pero el resultado es demasiado grande para ser correcta.
Para una estimación del límite superior podemos asumir que el grafo es completo. Esto no es completamente cierto, porque Android no permite la conexión de nodos cuando su camino va por encima de un nodo que no está ya en el camino (este extraño restricción significa que no podemos realmente representan Android combinaciones como ruta de acceso en un gráfico, debido a que los bordes para que se disponga o no dependiendo de que los nodos que ya incluido, una propiedad que ningún gráfico). Vamos a contar las opciones que usted puede hacer mientras que la elección de la contraseña: en primer lugar tiene que elegir el nodo inicial, entonces usted tiene que elegir el segundo nodo entre los ocho restantes, a continuación, elija el tercer nodo entre los siete restantes. También, desde Android requiere su camino para ser de al menos 4 nodos de largo, no tres, usted necesita elegir a otro entre los seis restantes. Esto le da a usted, hasta ahora $$9 \times 8 \times 7\times 6\times\dots$$ las opciones posibles. Aquí se puede elegir entre suspender o continuar por la elección de un quinto nodo: $$9 \times 8 \times 7\times 6\times (1 + 5 \times\dots)$$ mismo para las siguientes opciones, cada vez que puede elegir entre la suspensión y la elección de uno de los nodos restantes para continuar: $$9 \times 8 \times 7\times 6 \times(1 + 5\times(1 + 4\times\dots))$$ $$9 \times 8 \times 7\times 6 \times(1 + 5\times(1 + 4\times(1+3\times\dots)))$$ cuando todos los nodos se utilizan no tienes más opciones: $$9 \times 8 \times 7\times 6 \times(1 + 5\times(1 + 4\times(1+3\times(1+2\times(1+1)))))$$
poniendo todo esto en una calculadora el resultado final se convierte en $$985824$$ which is fairly a small number compared to other answers. As the number is pretty small, it is possible to count directly using a brute force algorithm. This has been done by a google engineer in here, and the result found by him for android unlock combination ($389112$) es menos de la mitad del valor que se calcula.
En realidad, en este caso la matriz de adyacencia y sus poderes pueden ser trivialmente calculada. Para un completo gráfico, de hecho, tenemos $A^m=n^{m-1}J$ donde $n$ es el número de nodos en el gráfico y en $J$ es la matriz de todos. Por lo tanto, el número de $f(n)$ de los posibles caminos de longitud $3, 4, \dots, n$ es exactamente $$f(n)=\sum_{k=3}^n\sum_{ij=1}^n (A^k)_{ij}=n^4\sum_{k=0}^{n-3}n^k=\frac{n^4(1-n^{n-2})}{1-n}$$ El número que se busca es $f(9)$.
Vamos a definir $v(n)$ como el número de $n$-paso rutas de acceso a una esquina particular, $e(n)$ a un lado en particular y $f(n)$ a el centro de nodo. Entonces usted tiene
$$v(n)=4e(n-1)+f(n-1)$$ $$e(n)= 4v(n-1)+2e(n-1)+f(n-1)$$ $$f(n)= 4v(n-1)+4e(n-1)$$
comenzando con $v(0)=e(0)=f(0)=1$. El resultado deseado es $$\sum_{n=3}^{n=9} 4v(n)+4e(n)+f(n)$$ que creo que puede ser 179,966,424.
Puede haber atajos: también es $f(3)+f(10)+2\sum_{n=4}^{n=9} f(n)$; para un gran $n$, el número de caminos de longitud $n$ es de alrededor de $8.860423 \times 6.36388667^n$, es decir, cerca de una progresión geométrica.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
