jueves, 21 de mayo de 2009

122. Resolución del concurso

En los comentarios al párrafo 120 pueden leer cómo se ha resuelto el reciente concurso. Sara, de Barcelona, España, ha ganado el prestigio internacional que se ofrece como premio aquí. Su respuesta acerca de que había que realizar una secuencia de nueve preguntas para averiguar el número es correcta y la fundamentación que ofrece es perfecta.

¡Felicitaciones Sara!

Me consulta Víctor qué relación tendría mi ayuda sobre analizar primero qué pasaría si sólo se tuviera el conjunto de los números UNO y DOS, como una forma de empezar a razonar el problema, con la fundamentación dada por Sara.

La respuesta es la siguiente: yo había pensado en una fundamentación del método levemente distinta a la propuesta por Sara, que pensaba que sería tal vez más fácilmente comprensible por los lectores, que les paso a contar enseguida.

Si alguien piensa y elige un número del conjunto dado por el UNO y el DOS es obvio que basta una pregunta para conocerlo.

Si luego alguien elige un número dentro del conjunto de los naturales entre el UNO y el CUATRO, se realizarían dos preguntas para conocerlo, por ejemplo: ¿es menor que tres? Si la respuesta es SÍ o si es NO, basta una sola pregunta más para conocer el número.

Si más tarde se elige un número entre el UNO y el OCHO, con la pregunta sobre si es menor que CINCO, cualquiera sea la respuesta, se cae en algo similar a lo del párrafo anterior. Por lo tanto, son necesarias tres preguntas.

Se sigue así hasta llegar al conjunto de los primeros 256 naturales que requiere ocho preguntas para determinar el número pensado. Como 273 (la cantidad de naturales propuesta en el enunciado) es mayor que 256 pero menor que su duplo (512), hacen falta 9 preguntas.
Yo había pensado iniciar la secuencia con la pregunta ¿es mayor que 256?
Si la respuesta es afirmativa, me queda un conjunto de 17 números que se resuelve con sólo cinco preguntas más, pero si la respuesta es negativa me queda un conjunto de 256 números que se resuelve fácilmente con ocho preguntas más, haciéndolas de modo de dividir el conjunto siempre en dos partes EXACTAMENTE iguales, según cuál sea la respuesta ofrecida.
De ahí venía lo que yo comentaba sobre que algunos subconjuntos pequeños de números podían, a veces, determinarse con menos preguntas que el máximo admisible en la secuencia programada de preguntas. Yo lo llamaba en ese comentario "tener suerte".
O sea que mi método es bajar de entrada el número de elementos para averiguar a algo de la forma 2 multiplicado por 2 multiplicado por 2... o sea 2 elevado a alguna potencia natural n, con la primera pregunta. Lo que sigue después de esa primera pregunta sería muy simple y faltaría hacer n preguntas más. Para el número 273 eso da 1 + 8 = 9 preguntas.

Un saludo cordial para todos y nuevamente, ¡Felicitaciones Sara!

No hay comentarios: