Cambalache 3,14 - La vidriera irrespetuosa


Que el mundo fue y será una porquería, ya lo sé.

Problema

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?
Es de Stanislaw Ulam y me lo recordó Juan de Mairena.

Recuerda la ética acertijera y espera 24 horas si sabes la solución.

2006-10-26 19:09 | Categoría: | 26 han comentado esto | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

URL de trackback de esta historia http://zifra.blogalia.com//trackbacks/44063

Comentarios

1
De: Sl.*? Fecha: 2006-10-26 20:58

Uisssssssss, justo cuando iba a clicar en enviar, he leido la ultima frase...

Pues nada, no respondo...



2
De: malambo Fecha: 2006-10-26 22:56

¿?



3
De: Zifra Fecha: 2006-10-26 23:04

¿y la mentira?



4
De: melocotoncito Fecha: 2006-10-26 23:06

Aunque lo primero que pensé fue algo parecido a #2, diría que el número de preguntas necesarias para adivinar la respuesta es 1 (ya que, teóricamente sería posible acertar por pura suerte, y el enunciado no lo descarta), y el número mínimo si el que pensó el número puede mentir una vez es dos (una para la mentira y la otra, preguntando por el mismo número, en un nuevo alarde de suerte, a la cual no puede mentir de nuevo). En cualquier caso, parece que el número de posibles respuestas no influiría en el número mínimo de preguntas, sino en la probabilidad estadística de que se dé ese afortunado éxito.

¿Gallifante? :P Prometo que no sé si he respondido correctamente.



5
De: Zifra Fecha: 2006-10-26 23:13

Pero tú has respondido a cuantas preguntas son posibles (mejor caso) no a cuantas necesita (peor caso).



6
De: Zifra Fecha: 2006-10-26 23:34

Malambo: te he borrado el comentario porque habías reventao la platilla de la página.

¿Algun <div> de menos?



7
De: Zifra Fecha: 2006-10-26 23:34

*plantilla



8
De: malambo Fecha: 2006-10-26 23:39

No, había sido un inocente link a:

http://zifra.blogalia.com/historias/43959



9
De: Zifra Fecha: 2006-10-26 23:54

:)



10
De: lightme Fecha: 2006-10-27 14:11

Bueno si usamos el algoritmo de busqueda binaria ( creo que asi se llamaba... ) jajajja no digo nada mejor que si no me linchan :)

A ver mita y mita de la mita y la mita y despues la siguiente mita no me sale la mita por que la tengo desconchavadita X'D ya ya le me callo ese estuvo fatal



11
De: Zifra Fecha: 2006-10-27 14:17

No, si la primera parte está cara. Pero ¿y si miente?



12
De: Akin Fecha: 2006-10-27 14:43

¿Se puede usar recursividad?



13
De: Zifra Fecha: 2006-10-27 16:30

sips



14
De: Dem Fecha: 2006-10-28 11:01

A ver, sin mentiras son lg base2 de n preguntas y con una mentira, de media, salen
(1+2+...+n)/n + (log base2 de n)

El primer sumando se podrá simplificar seguramente, pero para ser sábado por la mañana ya he pensado bastante.

Si esa es la respuesta explico el razonamiento, si no lo es, no lo explico ;P



15
De: Zifra Fecha: 2006-10-28 13:04

¿de media?

queremos el peor caso



16
De: Dem Fecha: 2006-10-28 16:15

El peor caso sería preguntar dos veces cada pregunta.
Es decir:
-¿Es menor que n/2?
-Sí.
-¿Es menor que n/2? (por si había mentido)
etc.

El peor caso es que mienta sólo al final o que no mienta con lo que tendríamos el doble de preguntas que en el caso en que no se pueda mentir, es decir: 2 log base 2 de n.

En mi respuesta anterior intentaba promediar el hecho de que puede mentir en la primera pregunta, o en la segunda o.... hasta la última.

¿Hay algún método más eficiente que repetir las preguntas?



17
De: Zifra Fecha: 2006-10-28 19:27



Creo :)



18
De: Fer Fecha: 2006-10-28 20:36

A ver cómo nos portamos los de letra.
¿Se trata de usar recursividad, no?
Parto de que se use el algoritmo de búsqueda binaria.
La captura de la respuesta se puede hacer con preguntas de validación tipo "¿en qué punto has mentido?".

Llamemos n el número máximo de preguntas necesario en caso de no mentir y m al ordinal de preguntas de validación. ¿Es el punto óptimo de intercalación de las preguntas de validación es n/2^m? O sea, la primera pregunta de validación se produce en n/2, la segunda a n/4, etc.

En ese caso el número de preguntas sería.
{Log base 2 de (log base 2 de n)}+{log base 2 de n)
(Recordad que soy de letras, no me pidáis que simplifique la expresión)
¿Hay gallifante?



19
De: Zifra Fecha: 2006-10-28 20:38

Vas bien, pero pienso que es mejorable. Me parecen que son demasiadas preguntas de validación :)



20
De: Fer Fecha: 2006-10-28 23:44

Después de la última pregunta, la que te da la solución, ya no hace falta hacer validación.
Por cierto es una pena usar sólo si/no. Si pudieses utilizar una característica y comparación la solución aparecería más rápido. Ejemplo en un acertijo popular: Tienes 9 perlas, una de ellas es falsa y se nota porque pesa menos. ¿Cuántas mediciones tienes que hacer en una balanza de platillos para encontrar la falsa? Eso va más rápido que el algoritmo de búsqueda binaria.



21
De: Fer Fecha: 2006-10-29 11:06

Va a ser que no.



22
De: lightme Fecha: 2006-10-30 02:01

Pero ¿y si miente?

Eha eso no es valido, esa es de cabrones y asi yo no me llevo, encima que hay que adivinarle el numero puede que me mienta :P

¿que tal si me miente?
anda tu...
¿Que tal si le meto una golpiza si llego al millon y sale que no?

Ademas recordemos la propiedad de densidad ( creo que va asi... ) un numero entre 1 y un millon podria ser un 3.1415... y entonces de que me sirve, las posibilidades son infinitas, pero ese seria el peor caso, el mejor seria que solo pensara en enteros...



23
De: Zifra Fecha: 2006-10-30 02:19

un número entero, hombre.



24
De: Akin Fecha: 2006-11-05 12:33

No se me ocurre como solucionar eso. Mi idea va por establecer preguntas de control cruzadas, tipo CRC, que permitan reconstruir la información a partir del punto en el que se descubra el error. Pero no se me ocurre un algoritmo que optimice eso.



25
De: malambo Fecha: 2006-11-05 16:47

A ver si anda esto:

Supongamos que el número elegido es el 37.

Caso 1
...
¿



26
De: malambo Fecha: 2006-11-05 16:54

bué. Juro que esta vez no he hecho nada, sólo texto puro... ah! y el símbolo 'menor'!

Número elegido: 37

Caso 1
...
¿menor igual 50?

¿me has mentido?

¿menor igual 50?

... (no hace falta seguir preguntando si ha mentido)


Caso 2
...
¿menor igual 50?
No
¿me has mentido?

¿menor igual 50?

... (no hace falta seguir preguntando si ha mentido)

Lo lamento, no puedo responder cuántas preguntas hacen falta. El procedimiento depende de cuándo el otro decide mentir. Esperemos que suba sin error. (Al menos no he reventado la plantilla.)



Nombre
Correo-e
URL
Dirección IP: 54.145.101.227 (5e587fe963)
Comentario

Busca en Cambalache


Blogalia


Se comenta en Cambalache

  • Pedro en Mariposas Imposibles
  • Anónima en 10 de Marzo de 1991
  • Anónima en Ya nunca juego al ajedrez Años de plomo (la película)
  • Anónima en No, no es la Diada ni son las torres gemelas de Manhattan...
  • Zifra en Olvido
  • Anónimo en Olvido
  • Zifra en Quantum State-Independent Contextuality Requires 13 Rays
  • Anónima en Álgido
  • nfernefer en Álgido
  • Zifra en Álgido
  • Categorías:

    Archivos:

    <Abril 2017
    Lu Ma Mi Ju Vi Sa Do
              1 2
    3 4 5 6 7 8 9
    10 11 12 13 14 15 16
    17 18 19 20 21 22 23
    24 25 26 27 28 29 30
                 


    Lista de Enlaces

    De interés

    E-góticos

    Mis otros

    FotoFlickr


    Blogalia



    Versión para la columna lateral


    zifra. Get yours at bighugelabs.com/flickr
    2003-2006 Zifra – Powered by Blogalia – Estadísticas: Nedstat Basic - Web site estadísticas gratuito El contador para sitios web particulares