Una persona piensa un número del 1 al 1.000.000, y otra debe adivinarlo haciendo preguntas que se contesten por si o por no. ¿Cuántas preguntas necesita?
Si la persona que eligió el número puede mentir una vez, ¿cuántas preguntas hacen falta?
27.5.04
691.- Descubra el número
Hace mucho que no posteaba un problem(it)a! Vamos con uno clásico de Stanislaw Ulam:
Si la persona que eligió el número puede mentir una vez, ¿cuántas preguntas hacen falta?
Si la persona que eligió el número puede mentir una vez, ¿cuántas preguntas hacen falta?
Suscribirse a:
Enviar comentarios (Atom)
3 comentarios:
AUTHOR: Matias
DATE: 05/27/2004 07:19:13 PM
Me parece que sale con 26, que es log_2(10^6) + log_2(20) + 1, la ultima para chequear si me mintio en las primeras 20 o me esta mintiendo ahora.
-----
AUTHOR: JuanPablo
DATE: 05/27/2004 11:21:31 PM
le encontraste la vuelta! pero esa cuenta da 27, me parece...
-----
AUTHOR: JuanPablo
DATE: 05/28/2004 12:08:22 AM
(y todavía se puede achicar el número de preguntas!)
-----
AUTHOR: Paul
URL: http://enredos.blogspot.com/
DATE: 05/28/2004 03:29:46 AM
Me gustó la solución de Matías, algo así había pensado yo, una mezcla de Busqueda binaria con un dígito verificador al estilo Hamming. Pero seguro que se puede bajar más.
-----
AUTHOR: itn
DATE: 05/28/2004 06:18:16 AM
Rectifico, el año de las respuestas correctas es dentro de 21 años. (me ayudó Andrzej Pelc.)
-----
AUTHOR: mariano
URL: http://uberbin.net
DATE: 05/28/2004 04:55:18 PM
juan.. vale cagarlo a palos hasta que me diga la verdad? :P
-----
AUTHOR: pini
URL: http://www.zonalibre.org/blog/mariposaenpekin
DATE: 05/28/2004 06:01:27 PM
mariano no te violentes, que es falta de comida.
pasá por la cocina.
-----
AUTHOR: JuanPablo
DATE: 05/28/2004 07:17:57 PM
ay, mariano... después te enojás si te dicen facho, facho ;)
-----
AUTHOR: mariano
URL: http://uberbin.net
DATE: 05/28/2004 07:43:32 PM
pero es una causa justa... :)
-----
:
AUTHOR: JuanPablo
DATE: 05/28/2004 07:47:26 PM
claro, claro... como la libertad y la democracia en Irak
(hablando de eso, hoy les eligieron presidente (!))
-----
AUTHOR: castroll
EMAIL:
IP: 200.109.62.42
URL:
DATE: 05/28/2004 09:54:59 PM
una forma humana de implementar el hamming seria asi:
escriba el numero elegido en binario (20 bits)
le pregunto uno por uno.
despues le digo:
escriba el nro de pregunta en la que mintio en binario (son 20 preguntas, asi que el numero es de 5 digitos). Si no mintio que escriba 0.
le pregunto uno por uno.
En total , 25 preguntas.
Se podria utilizar el hecho de que la persona que responde sabe cuando miente. O ir mechando la pregunta de la mentira mientras va diciendo los bits de esa manera 25 preguntas seria el peor caso, pero en promedio andariamos por las 22.5
AUTHOR: castroll
DATE: 05/28/2004 10:02:39 PM
que bolu, y si me miente en los 5 bits?,
bueh, ahi con los "bits" que sobran (son 21 posibles respuestas y con 5 bits hay 32 posibles, asi que no todas las combinaciones de 5 bits son validas) le hago hacer un hamming y que se mate calculando, yo le queria hacer un favor nomas.
-----
AUTHOR: JuanPablo
DATE: 05/28/2004 10:27:56 PM
jajajaja... no me diste tiempo a comentarte eso
hoy iba a postear la solución, pero cuando estaba posteando, se me colgó la máquina :((
-----
:
AUTHOR: castroll
DATE: 05/28/2004 10:38:54 PM
siguiendo el mismo razonamiento, que hubiera pasado si se te colgaba cuando escribias ese metapost? escribias otro mas cortito explicando?
-----
AUTHOR: JuanPablo
DATE: 05/28/2004 10:44:01 PM
claro, con sólo log_2 (del número original de caracteres)
-----
AUTHOR: pini
URL: http://www.zonalibre.org/blog/mariposaenpekin
DATE: 05/28/2004 11:06:20 PM
pero quién es castroll?
-----
AUTHOR: vqp
URL: http://sats.com.ar
DATE: 05/30/2004 09:21:54 PM
yo soy castroll.
Estoy leyendo este blog hace 2 o 3 semanas solamente y me gusto, los primeros comentarios que hice fueron un poco anarquicos y por eso aplique new_nick("vqp").
-----
AUTHOR: mariano
URL: http://uberbin.net
DATE: 05/31/2004 04:54:28 PM
le eligieron presidente con ese sistema? :S
-----
AUTHOR: TioPetros
URL: http://www.blogia.com/tiopetrus
DATE: 06/01/2004 10:57:44 AM
Qué pena haber llegado tan tarde a un problema tan bonito...
-----
AUTHOR: JuanPablo
DATE: 06/01/2004 11:58:32 AM
nunca es tarde, Petros, todavía faltarían postear las 25 preguntas ;)
AUTHOR: JuanPablo
DATE: 06/01/2004 12:03:04 PM
no mariano, supongo que preguntaron 'che, quien quiere ser el primer presidente democráticamente electo por nosotros de Irak?'
-----
AUTHOR: JuanPablo
DATE: 06/01/2004 12:04:17 PM
castroll / vqp bienvenido! (y esos mapitas satelitales están bárbaros!!)
-----
AUTHOR: funes, algo desmemoriado
DATE: 06/03/2004 09:42:11 PM
El problema de Ulam posteado, y sobre todo su variación con una mentira (o luego con 2 y en general con n) tiene una derivación insospechada y muy hermosa como modelo de las lógicas n valentes. La lógica clásica correspondería al caso clásico binario verdadero o falso. La vinculación entre este problema y las lógicas conocidas como de Lukasiewicz fue descubierta por el lógico italiano Daniele Mundici y pueden buscar los trabajos correspondientes on line, en particular, uno de sus alumnos encontró el número mínimo de preguntas (y la estrategia de preguntar óptima) en el caso general de que se admitan hasta "n" mentiras. Hay aplicaciones de este problema también en teoría de la información, en la cuestión de recepción de informaciones con posibles defectos en la tranmisión (necesidad de repreguntar).
Felicitaciones por el sitio, que me parece extraordinario.
-----
AUTHOR: JuanPablo
DATE: 06/03/2004 09:51:22 PM
hola funes, gracias por el comment y la información.
Por lo que veo, Mundici trabaja con varios de exactas!
Publicar un comentario