Lección
La teoría — Marcador matemático de direcciones Stargate
Una dirección de puerta es una selección ordenada sin repetición — una permutación. El orden importa (los mismos símbolos marcados en una secuencia diferente son una dirección distinta) y ningún símbolo se repite, que es exactamente el caso contado por P(n, k) = n! / (n − k)!.
Qué significa cada símbolo
n- el número de símbolos disponibles en el anillo:
39. k- cuántos se marcan:
7. P(n, k)- el recuento de selecciones ordenadas,
39! / 32! = 77,519,922,480. destinations- el recuento menor,
1,987,690,320— direcciones que realmente llevan a alguna parte, una vez que uno de los siete está reservado.
De dónde viene la fórmula
- Cuenta la marcación directamente. El primer símbolo tiene 39 opciones; el segundo tiene 38, porque ningún símbolo se repite; el tercero 37, y así sucesivamente para siete selecciones.
- Multiplicando:
39 × 38 × 37 × 36 × 35 × 34 × 33. Escrito con factoriales eso es39! / 32!, ya que el32!final es precisamente la parte no utilizada — que es la fórmula mostrada arriba,= 77,519,922,480. - Ahora fija el último glifo como el punto de origen, y solo seis quedan libres de los 38 restantes:
P(38, 6) = 38 × 37 × 36 × 35 × 34 × 33 = 1,987,690,320. Ese es el segundo número, y es exactamente el primero dividido entre 39.
Cómo leer lo que ves
Dos recuentos uno al lado del otro con la fórmula entre ellos. Lo interesante es su razón: la cifra de destinos es el total dividido exactamente entre 39, lo cual es la firma aritmética de haber reservado una de las siete posiciones.
- Supone
- Que ningún símbolo se repite y que el orden importa. Si descartas lo primero, elevarías 39 a la séptima potencia en su lugar; si descartas lo segundo, estarías contando combinaciones, que para 7 de 39 es menor por un factor de
7! = 5040. - Falla cuando
- Los recuentos grandes adulan una búsqueda. Casi dos mil millones de direcciones suena como una galaxia inagotable, pero un recuento de permutaciones no dice nada sobre cuántas son válidas — la mayoría de las secuencias no apuntarían a ninguna parte en absoluto, exactamente igual que la mayoría de las cadenas de siete letras no son palabras. Contar las posibilidades es la mitad fácil; saber cuáles significan algo es la mitad difícil, y ningún factorial te lo dirá.
Problema resuelto al detalle
-
Suma de comprobación para un preajuste de 7 glifos ponderado por 17( i + 3) 8 pasos
El ajuste preestablecido 7 glifos (estable) marca 3, 9, 17, 21, 28, 35, 1. El panel pondera el glifo de la casilla i —contando desde cero— por 17(i + 3), suma y reduce mod 97. Calcule la suma de comprobación a mano; a continuación, determine si marcar dos de esos glifos en orden inverso podría pasar desapercibido alguna vez.
-
Escriba primero los pesos, ya que todo lo que sigue es aritmética sobre ellos. Siete casillas, siete pesos, y aumentan en pasos de exactamente 17: esa regularidad es el motor principal de la demostración final.
-
Multiplique el número de cada glifo por el peso de su casilla y sume. Todavía nada es modular; se trata de una suma ordinaria y, si lo prefiere, se podría extraer 17 como factor común de todos los términos.
-
Ahora divida por 97 y quédese con el resto: 129 veces 97 entran exactamente en 12.597 y dejan 84. Eso es lo que marca la casilla Suma de comprobación (mod 97), y es la última cifra que esta deducción toma de la herramienta; todo lo que sigue es cometido suyo.
-
He aquí la pregunta que la casilla no puede responder. Intercambie los glifos de las casillas i y j: todos los demás términos de la suma permanecen intactos, por lo que el total varía en una sola cantidad (los dos glifos han intercambiado sus pesos). Al desarrollarlo, la diferencia de los pesos se reduce a 17(i − j), ya que los pesos forman una progresión aritmética con diferencia común 17.
-
Ponga a prueba esa fórmula en lugar de fiarse de ella. Las casillas 0 y 1 contienen 3 y 9, por lo que Δ = 17(0 − 1)(9 − 3) = −102, y −102 deja 92 mod 97, prediciendo 84 + 92 = 176, que es 79. Solicite a la herramienta los mismos siete glifos con los dos primeros intercambiados,
?address=9,3,17,21,28,35,1, y la casilla mostrará 79. -
Para que una trasposición pase desapercibida, Δ no debe ser simplemente pequeña, sino cero mod 97: la suma de comprobación tiene que volver a dar 84. Por tanto, 97 debe dividir a 17(i − j)(vj − vi). 97 es un número primo y no divide a 17, y un producto es múltiplo de un primo solo si uno de sus factores ya lo es: de modo que 97 debe dividir a la separación entre casillas o a la diferencia entre glifos por sí solo.
-
Ninguno de los dos puede proporcionarlo. Dos casillas distintas distan a lo sumo 8 entre sí, porque hay como máximo nueve chevrones; dos glifos distintos tomados del 1 al 39 difieren a lo sumo en 38. Ambas diferencias son distintas de cero y ambas son menores que 97, por lo que Δ nunca es 0 mod 97. Ninguna trasposición de dos glifos es invisible para esta suma de comprobación: ni para esta dirección, ni para ninguna dirección que se pueda marcar, porque nueve chevrones es lo que mantiene la separación entre casillas por debajo de 97. Si se le proporciona a la herramienta una dirección más larga a través de la URL, esa garantía es lo primero en desaparecer.
-
Detectar todas las trasposiciones no equivale a certificar la dirección, y aquí es donde la casilla se sobrevalora discretamente. De las 5.039 otras ordenaciones de estos mismos siete glifos, 62 también dan como resultado 84, cuando 97 bloques iguales darían alrededor de 52. Aproximadamente una ordenación incorrecta de cada cien se lee como correcta. Rechaza el error de marcado más común y nada más.
Respuesta
84 — y ningún intercambio de dos glifos puede dejarlo jamás en 84. Sin embargo, esa garantía es un límite, no una propiedad de las sumas de comprobación: solo se cumple mientras 97 sea mayor tanto que la mayor distancia entre casillas como que la mayor diferencia entre glifos. Amplíe el anillo a 98 glifos y desaparecerá de inmediato: 1, 98, 17, 21, 28, 35, 3 y 98, 1, 17, 21, 28, 35, 3 dan ambas 35 en la comprobación, porque su diferencia de 97 es anulada por el módulo (calculado aquí; el anillo de la herramienta se detiene en 39). Esa es precisamente la razón por la que los dígitos de control del IBAN se toman mod 97 en lugar de mod 10: elija un primo mayor que cualquier variación posible en el campo y todas las trasposiciones se verán forzadas a mostrarse. La herramienta calcula la suma de comprobación y no dice nada sobre lo que detecta, y la cifra de 62 en 5.039 es lo segundo que nunca calcula: aquello que le impide confiar en la casilla.
-
Referencias (1)
- Ordered selections without repetition, which is what P(n, k) counts: I. Niven, "Permutations and Combinations," in Mathematics of Choice: How to Count Without Counting, 7–26. Mathematical Association of America.