211service.com
Card Trick conduce a un nuevo límite en la compresión de datos
Aquí tienes un truco de cartas para impresionar a tus amigos. Dale una baraja de cartas a un amigo y pídele que corte la baraja, saque seis cartas y enumere sus colores. Luego, inmediatamente nombra las cartas que se han robado.
¿Magia? No exactamente. En cambio, es la mejor alternativa: las matemáticas. La clave es organizar la baraja con anticipación para que la secuencia de colores de las cartas siga un patrón específico llamado ciclo binario de De Bruijn. Una secuencia de De Bruijn es un conjunto de un alfabeto en el que cada subsecuencia posible aparece exactamente una vez.
Entonces, cuando una baraja de cartas cumple con este criterio, define de forma única cualquier secuencia de seis cartas consecutivas. Todo lo que tienes que hacer para realizar el truco es memorizar las secuencias.
Por lo general, este tipo de trucos surgen como resultado de algún nuevo desarrollo en el pensamiento matemático. Hoy, Travis Gagie de la Universidad de Chile en Santiago da la vuelta a las tornas. Dice que este truco lo ha llevado a un nuevo límite matemático en la compresión de datos.
Gagie logra este nuevo límite considerando un truco relacionado. En lugar de ordenar previamente las cartas, baraja el mazo y luego le pide a su amigo que saque siete cartas. Luego enumera los colores de las cartas, las reemplaza en el paquete y corta la baraja. Luego examina la baraja y dice qué cartas se robaron.
Esta vez, confía en la probabilidad para obtener la respuesta correcta. No es difícil demostrar que la probabilidad de que dos septuples de cartas tengan los mismos colores en el mismo orden es como máximo 1/128, dice Gagie.
Continúa considerando la probabilidad de predecir correctamente la secuencia de cartas extraídas al azar de una baraja de cierto tamaño y, después de algunos pasos adicionales, encuentra un límite inferior en la probabilidad de hacerlo correctamente.
Esto resulta estar estrechamente relacionado con varios problemas de compresión de datos y conduce a un límite inferior al que se ha encontrado por cualquier otro medio.
No conocemos límites inferiores anteriores comparables a [este], dice.
Eso es impresionante, un truco realmente genial en sí mismo.
Ref: arxiv.org/abs/1011.4609 : Límites de un truco de cartas