Adivinar un número del 1 al 1.000 con preguntas de sí o no: la solución
Algoritmia: pregunta sobre la búsqueda dicotómica, que divide el intervalo en cada pregunta.
El enunciado
Estoy pensando en un número entero comprendido entre 1 y 1.000. Puedes hacerme preguntas a las que solo respondo con sí o no. ¿Cuántas preguntas de sí o no bastan, en el peor caso, para adivinar ese número con seguridad?
¿Una pista?
No pruebes los números uno a uno: elige cada pregunta de modo que elimine la mitad de las posibilidades restantes.
Ver la respuesta y la solución
Respuesta: 10 preguntas: cada respuesta divide entre dos el número de posibilidades, y 2 elevado a 10 es 1.024, mayor que 1.000.
El razonamiento
Cada pregunta de sí o no reparte las posibilidades restantes en dos grupos, por ejemplo preguntando si el número es mayor que 500. Sea cual sea la respuesta, se conserva una mitad del intervalo y se repite el procedimiento sobre esa nueva mitad. Tras k preguntas, quedan como máximo unas 1.000 / 2 elevado a k posibilidades. Con 9 preguntas solo se pueden distinguir 2 elevado a 9, es decir, 512 casos, lo cual es insuficiente para 1.000 números. Con 10 preguntas se distinguen 2 elevado a 10, es decir, 1.024 casos, lo cual basta. La respuesta es, pues, 10 preguntas en el peor caso. Este principio es el de la búsqueda dicotómica, de complejidad O(log n).
¿Y ahora?
El razonamiento se entrena como la memoria: practicando a menudo. Ponte a prueba después con nuestros quiz de cultura general.