jueves, 7 de mayo de 2009

116. Un nuevo concurso

Algunos lectores insisten sobre la posibilidad de encontrar aquí nuevos concursos.
De acuerdo, ahora tengo un poquito más de tiempo y voy a ver qué pasa con éste:

Una persona piensa en un número natural (1, 2, 3, ... etc) entre el 1 y el 273, ambos incluidos) y sólo aceptará preguntas que se respondan por sí o por no, tendientes a determinar cuál es ese número.

Se desea saber cuál es la mínima cantidad de preguntas que se deben realizar para determinarlo con seguridad. Además de esto, se espera una reseña de cuáles serían esas preguntas.

¡Buena suerte para todos!

5 comentarios:

Víctor dijo...

Hola Roberto.

La mínima cantidad de preguntas posibles es UNA.

Se trata de preguntar: ¿has pensado el número 100?... y tener la suerte de que el otro diga SI. En tal caso, has hecho una pregunta y has determinado el número con seguridad, por lo que la respuesta cumple con la literalidad del planteamiento.

Y es la única respuesta posible. La solución que a primera vista se le ocurre a uno (ir cerrando el número en cuestión estrechando los márgenes), no sería nunca apta para determinar "la mínima cantidad de preguntas"... pues dependería igualmente del azar que acertases a la primera, o después de agotar el número máximo de preguntas posible.
Se podría obtener matemáticamente el número máximo posible de preguntas, pero el planteamiento pide "el mínimo"

Saludos.

Roberto dijo...

Víctor, al leer tu respuesta me doy cuenta de que no he sido claro en la letra del planteo que quería hacer: en eso tienes razón. Hay un par de detalles que no tuve en cuenta y que tú me marcas muy correctamente.
El enunciado debería decir algo así como:
"Diseñar un esquema o algoritmo de preguntas que, sea cual fuere el número que se ha pensado (en el rango del 1 al 273, por ejemplo), minimice la longitud del proceso de búsqueda. Esa longitud viene dada por la cantidad máxima de esas preguntas a realizar (que sólo pueden responderse por sí o por no) tendientes a conocer con certeza dicho número."
Lo que yo había pasado por alto es que para ciertos rangos de números propuestos existe la posibilidad cierta de que algún subconjunto de esos números se pueda determinar con algunas preguntas menos que el máximo previsto por el algoritmo para tener la certeza de determinar a cualquiera de ellos, sea el que fuese el elegido.
Esos números "privilegiados" dependen de cómo se ha diseñado el algoritmo.
La clave es que donde puse "con seguridad" debería haber puesto: "con seguridad, sea cual fuere el número elegido".
En realidad, en cualquier algoritmo de búsqueda se definen tres longitudes que se denominan la longitud del mejor caso (cuando uno tiene suerte...), la del peor caso (cuando uno tiene una especial mala suerte...) y la longitud promedio (se hace un promedio ponderado de las posibilidades de éxito).
En el algoritmo que yo propongo para esta búsqueda la longitud promedio y la del peor caso, prácticamente coinciden, aunque la del mejor caso puede ser realmente mucho más corta para ciertos subconjuntos de números "más facilmente hallables" debido al rango de números propuestos (del 1 al 273) y a los detalles particulares (que no puedo revelar por ahora...) del diseño del algoritmo utilizado.
Sin duda, tu respuesta me puso a pensar en una cierta cantidad de cosas que había pasado por alto al escribir el concurso y. por otra parte, cumple con la literalidad de la propuesta. Sin embargo, me interesaría que alguien diera con el algoritmo que yo pensaba. Así que voy a hacer dos cosas: la primera es que te declaro ganador de este concurso, ¡felicitaciones!. La segunda es que voy a poner un nuevo párrafo comentando que quisiera que alguien se interesara en resolver un nuevo concurso con su enunciado redactado sobre la base del ya propuesto, pero con las correcciones que te comenté más arriba.
Así que, felicitaciones nuevamente y muchas gracias por haberme hecho pensar más profundamente en este tema.
Un abrazo.

Víctor dijo...

Hola Roberto :)... ¡pues muchas gracias por declararme ganador!
Ya conoces mi técnica para resolver los problemas, a falta de conocimientos matemáticos: llevarlos a la práctica y, viendo cómo se desarrollan, intentar descubrir la "fórmula" que los rige.
En este caso ocurrió así, y bien pronto advertí que el número de preguntas necesarias no era igual en todos los casos... no era lo mismo que el número a buscar fuese el 136, a que fuese el 208.. incluso una pregunta podría valer si tenías suerte.. y tal como habías formulado la pregunta al principio, la respuesta UNA llegaba a encajar.. dudaba si era un planteamiento "trampa", o si estabas realmente buscando la respuesta que pides en este planteamiento más extenso.
Desde luego, el interés matemático está en esta segunda opción, y disfrutaré leyendo la solución cuando alguien la ofrezca.
Saludos!

Roberto dijo...

De acuerdo, Víctor. Pero me gustaría contarte entre los candidatos a obtener la resolución.
La respuesta se puede llegar a obtener y a relatar sin una matemática muy elevada ni notación demasiado especializada.
Sólo una pequeñísima ayuda para ti y para todos los demás interesados:
Es conveniente pensar primero cuál sería la respuesta al problema planteado si el rango de números fuera tan breve como solamente el UNO y el DOS.
Saludos cordiales desde Buenos Aires.

Myriam dijo...

¡Sorprendente Vìctor!, felicitaciones, en algún rato que tenga yo tambièn pensaré en la solución. Saludos!