Escribe Superpanzeta:
Un agente secreto londinense informa de sus actividades todos los días a sus superiores por medio de un anuncio por palabras en un periódico.
El anuncio consiste siempre en un único carácter (letra, número, símbolo o signo de puntuación), casi siempre diferente del del día anterior.
Para asegurar la máxima confidencialidad, el agente ha pactado con su colateral el siguiente procedimiento:
Cuelga una hoja de periódico en la pared y lanza un dardo las veces que sea necesario para que el dardo quede clavado en una letra, número o signo de puntuación.
Este carácter, que ha sido elegido aleatoriamente, es convertido en un número binario de 7 bits por medio de una tabla ASCII (ya que es londinense, no tiene que preocuparse de letras acentuadas o eñes).
Finalmente, el agente modifica como máximo un único bit de los 7 (cambia un 1 por un 0, o un 0 por un 1), pudiendo también dejar la palabra de 7 bits sin modificar.
Usando otra vez la tabla ASCII, el agente obtiene la nueva letra o símbolo que utilizará como texto del anuncio.
Supondremos aquí que el carácter producido siempre se puede imprimir. En caso de obtener uno de los caracteres invisibles de la tabla ASCII, siempre podemos hacer que se repita el lanzamiento del dardo y la posible modificación de 1 único bit hasta que el procedimiento produzca un carácter visible.Ejemplo: El dardo aterriza en una «r». El código ASCII es 114 (1110010).
El agente modifica un bit (por ejemplo el tercer bit empezando por la derecha) y obtiene 1110110, que equivale al carácter ASCII 118, «v».
El agente publica un anuncio con el texto «v».La comunicación establecida de este modo es completamente unidireccional.
El código ASCII obtenido lanzando el dardo se puede considerar aleatorio a todos los efectos. Ni el agente ni sus colaterales son capaces de predecirlo de antemano.
Es perfectamente posible que se repita el código inicial, o el final, o ambos, del día anterior.
El desafío consiste en averiguar cuántos bits de información diaria puede transmitir el agente, y dar un ejemplo práctico de cómo conseguirlo.
Respuestas a desafiossanti@gmail.com hasta el lunes a las 23:59. Este mensaje se autodestruirá en 3, 2, 1…
Por cierto, os pongo aquí un artículo sobre los desafíos en La Gaceta de la RSME (ver: http://gaceta.rsme.es/vernumero.php?id=85):Desafíos_El_País
Agradecimientos: a Bruno Salgueiro por enviérmelo y a Adolfo Quirós por mencionar otra vez el Blog en su artículo.
Santiprofemates 
SuperPan returns!
Espero que el desafío sea mejor que la película. :)
OK. Un nuevo desafío.
¿Sabéis algo de Pixe?
Un saludo,
Pues no, de momento no sabemos nada.
Esperemos que esté liado y se haya despistado.
No problem.
Un saludo,
Hola Superpan, me lo pones difícil. Es un campo que no domino, y para colmo (entiéndase dicha por otro lado) voy a estar unos días fuera.
Por si tengo tiempo para aburrirme, a ver si me aclaras algo el tema.
Entiendo que lo que se está pidiendo es que se detalle un código (que van a conocer las dos partes) de manera que con sólo un carácter se transmita el máximo de información posible. ¿Es así?
Interpreto que esa información puede pasarse en el idioma o lenguaje que queramos (porque ambos también lo sabemos).
Sobreentiendo que a la hora de contabilizar bits (si es que hay que hacerlo), se tenga que tomar como referencia el ASCII (que dicho sea de paso sólo lo conocía de oidas)
Como ves hago preguntas un tanto insulsas pero insisto es que en estos temas estoy un poco perdido.
A priori se me antoja un tanto ilimitado, quiero decir que no habiendo más requisitos o condicionantes que los expuestos la imaginación podría llegar muy lejos. ¿O sólo hay una respuesta posible?. Seguro que no lo he entendido bien.
Veamos.
El idioma no tiene nada que ver. Puede ser cualquiera. Elegí Londres como escenario porque el código ASCII para los caracteres comunes y las letras no acentuadas ocupa sólo 7 bits. Si usáramos un periódico español, podríamos necesitar 8 bits. En realidad no es necesario que la palabra de 7 bits sea un carácter ASCII. Lo he novelado así, pero se trata simplemente de una palabra aleatoria de 7 bits.
Las dos partes se conocen y acuerdan el código de antemano.
Se trata de transmitir información genérica no determinada. Es decir, bits. La información enviada a lo largo de los días puede estar codificada en ASCII o ser cualquier otra cosa. Ya sabes, cada bit te da dos posibilidades: 0-Estoy mal, 1-Estoy bien (por ejemplo). La información transmitida no es importante. Sólo importa la cantidad de la información (en número de bits).
Hay más de una solución posible. Puedes lanzar tu imaginación todo lo lejos que quieras.
Por supuesto, hay que transmitir ese máximo número de bits con las limitaciones del problema.
Y buen viaje!
Me pierdo, ¿palabra?, me pareció entender que lo único que va a salir es una letra.
Sí. Una «palabra» binaria de 7 bits. Piensa en los bits como si fueran letras. Esa «palabra» binaria equivale en código ASCII a una única letra de nuestro alfabeto, que es lo que publica el agente.
Pero siguen siendo 7 bits.
A ver si lo he entendido:
– partimos de 7 bits aleatorios
– podemos (o no) modificar uno de esos bits
– después de modificado el bit, y según el código acordado, los 7 bits resultantes transmiten n bits de información, es decir, n informaciones si-no.
– hallar uno de los códigos (puede haber más de uno) para que n sea máximo.
Superpan, si lo he entendido bien, sólo una pregunta más: ¿tenemos que demostrar que nuestra solución es la máxima? Es decir, si a mí me sale n=18 (he elegido un número imposible a posta) tengo que demostrar que n=19 es imposible?
PD: ¡Qué bien me siento haciendo preguntas como si supiera por dónde coger el problema! No tengo ni idea de cómo empezar.
Más que código, yo lo llamaría procedimiento, pero sí, creo que lo has entendido.
En cuanto a demostrar qué n es el máximo, es tan trivial que es evidente y no necesita demostración. Pero tú mismo…
Vale, si es trivial es que lo estoy haciendo mal. :(
Si crees que lo estás haciendo mal es que por lo menos estás haciendo algo.
Por curiosidad, ¿qué estás haciendo? :)
Te lo digo en un correito, más para no condicionar a la gente con mi solución cláramente errónea que por que para no chafar el desafío.
Muchas gracias. Un detalle de tu parte. Iba a proponértelo pero no ha hecho falta. Así da gusto.
Si tan mal se entiende no os cortéis, ¿eh?
Preguntad a saco.
yo tampoco lo entiendo, lo volveré a leer mañana o pasado.
Porque no creo que lo que preguntes es cuántas palabras distintas hay de 7 bits, o sea, desded el «0000000» hasta el «1111111»…
Haces bien en no creerlo.
El resumen de José Luis de más arriba es correcto. Seguramente lo entenderás mejor que mi novela.
Hola Superpanzeta
Te he enviado un mensaje relativo a la interpretación del desafío, que no he querido comentar aquí por si prefieres que no se den pistas.
Participar en este blog es un gustazo.
Enhorabuena a Santi por haber reunido gente como vosotros y gracias a tí Pardillano por tus buenas intenciones y tu discreción. Tienes la respuesta en el correo, y espero tus comentarios con interés.
Yo entiendo que el receptor del mensaje, a la vista del caracter imprimible que aparece, es capaz de determinar cual es el bit modificado, y eso a su vez le puede dar mas información de que bits no modificados son aprovechables. ¿Van por ahí los tiros?
No. Al menos en mi solución, no hay manera de saber qué bit se modificó. Ni siquiera se puede saber si se modificó alguno.
Pero mi solución no es ni la mejor ni la peor.
Si eres capaz de averiguar qué bit se modificó y eso te lleva a igualar el número de bits transmitidos de mi solución, perfecto.
A mí no se me ocurre cómo conseguirlo, pero eso no significa nada.
Tú dispara, que tienes licencia para divagar…
Me ha gustado el desafío. Y creo que ha estado bien planteado desde el principio.
Gracias. Me alegro de que te guste el desafío, y espero que te siga gustando tanto como a mí tu primer intento de solución. Sigue así.
Yo también pienso que el desafío está bien planteado, pero claro, mi punto de vista no cuenta.
Os voy a dejar una pista muy sutil, aunque hay ya alguien muy bien encaminado que no la necesita.
Echarle un par de miradas a esto a ver qué os sugiere:
https://docs.google.com/open?id=0B4CZEVLXRqvUUGgzakZ6Y09UZFN0SWJ1WU90dk1DUQ
Bueno, lo he vuelto a leer hoy, y sigo sin entender lo que se quiere. Porque si siempre se transmiten 7 bits, ¿Cuál es el número máximo de bits que se transmiten? Pues 7, ¿no?
Jc, se pregunta por los bits del mensaje diario del agente. Los 7 bits originales son aleatorios, y por tanto no transmiten información alguna y no forman parte del mensaje del agente. Recuerda que el agente no tiene control sobre ellos. Son aleatorios.
Una vez cambiado (o no) un bit, el resultado ya no es completamente aleatorio, y por tanto permite transmitir alguna información.
De los 7 bits recibidos se puede extraer un número n (inferior a 7, claro está) de bits útiles de información, que forman el mensaje diario del agente.
Más claro:
El agente quiere transmitir n bits. Usando sus n bits de información debe manipular una secuencia desconocida de 7 bits (cambiando como máximo uno de ellos) de forma que se puedan extraer esos mismos n bits del conjunto (posiblemente modificado) de 7.
Bueno, como ya han pasado unas cuantas horas y no veo movimiento, os voy a orientar con la pista del link que os dí:
https://docs.google.com/open?id=0B4CZEVLXRqvUUGgzakZ6Y09UZFN0SWJ1WU90dk1DUQ
He tratado de representar (sin éxito) una especie de página de periódico con uno de los posibles mensajes del agente, en el ejemplo, la letra M.
Quería haber puesto un titular sobre la ex-ministra Aído como pista, pero era muy difícil de encajar en un dibujo tan pequeño de forma que siguiera funcionando.
¿Que siguiera funcionando?
Pues sí. Si os fijáis con detenimiento, la página del periódico es un código QR (o BiDi) no demasiado disfrazado.
Me apresuro a deciros que los códigos QR / BiDi no tienen nada que ver con el desafío. Sólo lo he usado para llamar la atención sobre algo que sí es una pista.
Para aquellos con un teléfono con lector de códigos, os sugiero que os descarguéis el fichero y lo ampliéis en la pantalla para escanearlo con el móvil. Como podréis comprobar, el código sigue funcionando.
¿Por qué digo «sigue»? Pues porque evidentemente, el código original no tenía ese aspecto. Para empezar, la cabecera de El Pais se come varias filas de pixeles. He puesto líneas blancas para simular columnas y párrafos que también se comen un montón de píxeles. He borrado un área rectangular entera de píxeles para colocar la letra M sobre fondo blanco. He añadido ruido aleatorio. He escalado el fichero con un factor de reducción no entero que deforma los píxeles. Y he copiado y pegado otro trozo debajo para alargar la «página».
Como podéis ver, he manipulado bastante el código QR original, pero éste sigue funcionando. ¿Por qué? Pues porque tiene redundancia y es incluso capaz de corregir los errores.
En la misma línea iba lo de la ex-ministra y la «paridad» que no llegué a poner.
¿Qué os quiero decir con esto? Pues que mi solución al desafío está inspirada en los conceptos de paridad. O mejor y más exacto, redundancia.
Por si alguien se lo pregunta, la página de periódico dice:
«Mándame un correo con el asunto PISTA»
Mi idea era explicar todo esto en privado para los que fueran enviando correos, y finalmente explicárselo a los demás aquí.
Como veo que me ha salido rana el experimento, esta es la explicación, y esta es la pista:
Pensad en sistemas de redundancia y corrección de errores.
Intentaré dar con la solución a este nuevo desafío siempre y cuando tenga tiempo.
Con el anterior pude dedicarme a él.
Un saludo,
De hecho, lo imposible siempre es demostrable.
Un saludo,
Bueno, este no es imposible. Espero que también puedas demostrarlo.
Ánimo.
Paquito SuperPanZ, gracias por los ánimos.
Como he dicho espero tener tiempo. Tengo un gran atasco de correos.
Un saludo y buen finde,
No lo pillo, no lo pillo…
Me está dando la sensación de que cuando vea la solución pensaré que es magia, como me ocurrió con la de los 4 ases o con la de las bombas: algo que parece imposible y cuando te lo explican ves que no lo es.
Por cierto, este mensaje es mío, no sé por qué no pone mi nombre.
Mira que eres exagerado. Si casi lo tienes…
Aunque lo parece (de ahí su gracia), este desafío no es imposible.
Eso sí, tiene 2 problemas:
1-No es fácil.
2-Me explico fatal.
Así que no me importa ir dando pistas y explicaciones.
¿Ya tienes calculado el máximo número de bits?
El hecho de hablar de que sea imprimible quiere decir que trabajamos entre el 0100000 y el 1111111. ¿Es esto importante o intrascendente?
Totalmente intrascendente.
Lo de imprimible era sólo para que encajara en el procedimiento del periódico. Tienes todo el rango de 7 bits para jugar.
Vislumbro caminos que finalmente no llevan a ningun sitio. Pares o impares, agrupados o sin agrupar, al principio o al final, Cuantos llevan sombrero y cuantos no, son hombres todo lo que parece o son mujeres, ¿cuantos matrimonios hay?.
Reconozco que no es fácil dar con una solución, pero los conceptos no son complicados. Está claro que no has seguido el camino de pares o impares hasta el final.
Hay una técnica de corrección de errores que se parece tanto a mi solución que os debería servir de inspiración.
¿Tienes al menos acotado el número de bits a transmitir?
Por algún motivo que no acabo de comprender, la gente parece no tenerlo claro.
Como veo que hay 2 participantes que se han tomado en serio lo de que el carácter tenga que ser imprimible, lo repetiré aquí en beneficio de todos:
No tiene por qué ser un carácter imprimible. Era sólo para que la historia del periódico encajara.
Imaginad si queréis que lo que publica el agente es un texto con 7 dígitos (unos y ceros). Hay 128 posibles textos a publicar, no sólo los imprimibles.
Os pido perdón por no haberlo dejado claro.
Nuevamente felicito a Superpanzeta, por este problema y por ser un gran animador de este blog. Creo que su planteamiento del problema es impecable, aunque él es muy modesto. Quedan dos días para divertirse y tratar de encontrar una solución propia.
De primeras los deafíos de SuperPanz me desconciertan bastante, pero he de reconocer que están francamente bien y que me han abierto nuevos horizontes. Espero haber atinado con lo solicitado, desde luego si no husiese dado tantas pistas aún andaría perido en el monte, enhorabuena.
Pensé dejarlo estar, porque nos avisaba SuperpanZ que no era fácil, y por las pistas pensaba que me tocaba aprender métodos de detección y corrección de errores para poder resorverlo…
Pero no, resulta que sí que se puede hacer, sin complicaciones.
Así me gusta. Que la gente no se rinda. JC, siento que el enunciado te resultara tan opaco.
Lo de la detección y corrección es sólo para inspirar. Puedes usarlo a fondo, o no. En el fondo, el concepto clave es la paridad. No es necesario más. Bueno, quizá darse cuenta de que con una no basta (¡y esto va a ser mi última pista!). :)
En cuanto a la dificultad, bueno, me remito a los resultados. No tengo ningún otro criterio objetivo porque mi opinión no sirve, pero ya os comentaré de dónde salió este problema, y la calificación del autor del libro era «difícil». No me extraña, porque su solución no hay quien la entienda.
Bueno, supongo que cuando todo el mundo vea las soluciones que se han mandado (por lo menos las simples) pensará que no era tan difícil.
Era lo que pretendía, después de todo. Que parezca imposible (o por lo menos complicadísimo) y luego no lo sea.
Gracias por perseverar.
Y a los demás: ¡ánimo!
No, no, si el enunciado está bien. Digo que parece más difícil de lo que es para que la gente no se rinda.
Ya lo habéis oído.
Me comenta JC una cosa interesante, que curiosamente guarda relación con el comentario que añadió Santi bajo el desafío.
http://gaussianos.com/presentacion-de-la-serie-desafios-gaussianosyguijarro/
Yo por lo pronto y por lo que he visto de Gaussianos, carezco de nivel matemático para participar, pero si mantienen la filosofía de El País sí que me animaré. Creo entender que va a haber un desafío mensual, así que no debería afectarnos mucho.
Sólo espero que esto no perjudique la audiencia de Santi.
Por otra parte he pensado que podríamos comentar su desafío tal como se venía haciendo con el de El País.
Y que haya un premio en forma de libro no está nada mal.
Considero que en el fondo es una buena noticia, y que no debería interferir con nuestros desafíos. ¿Qué os parece?
P.D. Aprovecho para comentar que el link sobre los desafíos que dejó Santi es muy entretenido e ilustrativo.
El blog de Gaussianos es magnífico y me alegro de esta iniciativa, otra cosa es que pueda partcipar en él por el nivel del mismo. No creo que perjudique a la audiencia de Santi, más allá que que tengamos más trabajo. Sobre comentarlos aquí lo veo más complicado porque Gaussianos ya tiene sus propios comentarios y entiendo que se podría ver como una competencia desleal. No se trataría de abandonar un blog por otro, si no apuntarse a los dos, mientras el cuerpo aguante.
Opino lo mismo que tu. Se puede seguir el desafío mensual en gaussianos y el semanal en santi.
Sí. Yo tengo Aleph sub-cero tonterías para repartir, así que no se debería notar.
Por fin. Ahora que lo he pillado, confirmo que el planteamiento es absolutamente correcto.
He de decir que en mi caso, estaba inicialmente totalmente desconcertado. Intuí por donde iban los tiros, pero no me acababa de cuadrar. Yo estaba vislumbrando un problema diferente. La única explicación que hallé es que había errores en el planteamiento e incluso escribí a SuperPanZ sugiriendo un planteamiento alternativo. ¡Que pretencioso por mi parte!. El planteamiento de SuperPanZ es correcto y yo era el que estaba totalmente perdido. Gracias, SuperPanZ por no haber dado detalles en público de mis comentarios. Ahora me avergüenzo de ellos.
Respecto a los comentarios posteriores de SuperPanZ, reproduzco los que a mi juicio son más relevantes:
«Hay una técnica de corrección de errores que se parece tanto a mi solución que os debería servir de inspiración»
«mi solución al desafío está inspirada en los conceptos de paridad. O mejor y más exacto, redundancia»
Enviaré mi solución esta tarde/noche.
De nada, Christian, aunque no sé por qué.
Caramba, este blog se parece a los jardines de Versalles. ¡Qué gente más educada!
Tu intención estaba clarísima: ayudar. Y fuiste absolutamente correcto y amable. Así que las gracias son para tí.
A mí me parece que tu propuesta te honra y no veo motivo de vergüenza alguno. Al principio no entendiste del todo el problema, pero hubo otros que no entendieron nada, así que de haber alguien que no esté orgulloso soy yo. Es obvio que el planteamiento se puede mejorar.
A veces pienso que tengo un don para despistar.
En cuanto a las pistas, sí, esas que has elegido no están mal (aunque por lo visto depende de quien las recibe). Desde luego son mejores que mi tontería QR, pero yo diría que la mejor es la de que «con una no basta».
No te líes mucho,
Paquito SuperPanZ
Enhorabuena SuperPan, me has vuelto a vencer. Intuyo por dónde van los tiros pero no he podido dedicarle todo el tiempo que me hubiera gustado. Seguro que la solución resultará ser de una sencillez desarmante. Espero con ganas verla mañana. Gracias por el buen rato.
Otra vez será. Si te has entretenido, es más que suficiente.
Gracias por intentarlo.
He regresado hace un ratito, voy a ver si se puede retomar el asunto. Cuando me fui no había entendido lo que se pedía, veremos a ver si leyendo lo anterior consigo comprender algo más.
Ya te diré Superpan, si veo o no veo nada.
Vale, como te queda un suspiro, si encuentras la idea en plan informal, te relevo de la obligación de redactar una solución completa y detallada.
Y si no puedes, no pasa nada. Repites en Septiembre y ya está. XD
Creo que ya voy entendiendo lo que se pide, ahora «sólo» falta buscar la solución.
Se me ocurre empezar por una de estas dos vías:
La genética o la electricidad.
¿Cuál es más apropiada en este supuesto?
Ninguna de las dos, seguro.
Se te ha acabado el tiempo, colega. Nos vemos en Septiembre. Jajaja!
Ah, los estragos de la Cincomarzada… :)
Esta vez no he podido participar.
Un saludo,
No he tenido tiempo. Eso ha sido todo.
Un saludo,