El principio de Kruskal

Criba de Erastóstenes

Hace ya algún tiempo llegué hasta la web de la Hoja Volante a través de un link sobre origami que me habían enviado. Allí descubrí el Principio de Kruskal. Déjenme que les cuente.

Elige una palabra del primer párrafo. Luego cuenta el número de letras que tiene y avanza tantas palabras como letras tenga esa palabra. Llegarás a otra palabra. Repite el proceso. Seguramente (si no me he equivocado contando) tu secuencia de palabras recorrerá las palabras marcadas en negrita en este párrafo terminando exactamente aquí.

Bien, podrían pensar que puedo predecir el futuro, o quizás que he hecho trampas. Seguramente he preparado el texto para que esto pase. Al fin y al cabo es poco realista pensar que, por casualidad, desde cualquiera de las primeras 33 palabras de este texto se llegue al mismo lugar tan sólo medio párrafo después. ¿O no?

Pues resulta que no me ha hecho falta trucar el texto. Simplemente he escrito los primeros dos párrafos y luego he iterado el proceso empezando por “Hace”. Al cabo de un rato he llegado a la palabra “otra“. Luego he probado algunas palabras más: “Kruskal”, “Déjenme”, “Cuente”… y con todas ellas se llegaba a “otra“. En realidad tampoco hace falta comprobar muchas, el Principio de Kruskal nos asegura que acabaremos en la misma secuencia rápidamente.

Veamos el porqué: Si tienes una secuencia ordenada cualquiera de números naturales (menores que una cierta cota K) puedes realizar el algoritmo descrito anteriormente, eliges uno de los primeros, te mueves un número de posiciones igual al número escogido y vuelves a repetir el proceso. Al cabo de un rato seguro que llegas a una determinada posición empieces donde empieces. Intuitivamente podemos comparar este proceso a la Criba de Erastóstenes. Si escogemos un punto inicial y aplicamos el algoritmo tachando los números (o palabras) que visitamos. Cuando escojamos otro punto inicial y repitamos el proceso seguramente en algún punto llegaremos a un número (palabra) ya tachado. A partir de ahí las dos secuencias serán iguales.

Como los números (palabras) no pueden crecer eternamente (son menores que una cierta cota K) la cosa no se nos desmadrará mucho y seguramente, a la larga, todas las secuencias se acaben uniendo empiecen donde empiecen. Por supuesto hay secuencias que son una excepción a esta regla (sin ir más lejos: “2, 2, 2, 2, 2, 2, …”) pero eso no importa, porque la Ley de los Grandes Números de Estadística nos asegura que en una secuencia infinita aleatoria hay probabilidad cero de que se formen los patrones necesarios para que el Principio de Kruskal no funcione.

Como el Principio de Kruskal necesita muy pocas hipótesis y en general funciona muy bien (las secuencias convergen rápido si K es pequeña) suele usarse como truco de magia con palabras o cartas (donde K <14 en general).

Pueden aprender más sobre Cartomagia matemática y cartoteoremas mágicos gracias a este PDF de Venancio Álvarez, M. Auxiliadora Márquez y Pablo Fernández (Universidad Autónoma de Madrid).

Escrito en 05/11/07 09:16 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

Coooooooooool!!!!!!!!!!!!!!!!!!!!!!!!!

rf microwave components | 02/12/14 04:38 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)