Tengo una serie de números del 1 al N. Un sistema selecciona aleatoriamente dos números y calcula su suma y el producto. Tengo que adivinar la suma y el producto, El sistema le indicará si la suma y el producto son más grandes o más pequeños. ¿Cuál es la estrategia óptima para encontrar los números de número mínimo de aciertos.
Respuestas
¿Demasiados anuncios?
Marconius
Puntos
4276
Supongo que estamos buscando una estrategia minimax que limita el número de conjeturas requerido en el peor de los casos. De lo contrario, si estamos buscando minimizar el número esperado de conjeturas, vamos a la necesidad de adaptar la solución para que pueda obtener una mayor rentabilidad en el caso promedio, por ejemplo, mediante la elección de más probabilidades de combinaciones.
El producto le dará mucha más información que la suma (en los casos donde uno de los números es una de las prime $\ge \sqrt{N}$ se dirá inmediatamente que ambos números). Será más eficiente si se utiliza el producto y la suma conjeturas en un complemento de moda, adivinanzas, decir, productos que en el lado de alta y de las sumas en el lado de baja. Así que yo sugeriría una búsqueda binaria sobre todos los valores posibles del producto, mediante la suma de excluir otras posibles combinaciones. Por ejemplo:
- para N=4: posibles productos de se $\{2,3,4,6,8,12\}$, de modo que usted puede comenzar con inicial conjeturas de $p=6, s=5$. Si uno o ambos de estos es correcta, usted sabrá que los dos números de inmediato; de lo contrario, un segundo supongo que debería permitir a usted para determinar los números.
El siguiente diagrama pone de manifiesto que lo que estamos haciendo en realidad es una de dos dimensiones de búsqueda. Puede que desee adoptar alguna heurística para adivinar $p,s$ en cada etapa: por ejemplo, minimizar el número máximo de puntos por encima de todos los cuadrantes (suponiendo que ambas suposiciones son erróneas). Si este es de dos o tres, el siguiente supongo que siempre va a determinar los números; si cuatro, el siguiente supongo que sólo tendrá éxito si hay dos o tres (pero no cuatro) números con la misma suma o el producto.
freethinker
Puntos
283
La siguiente estrategia reduce el número de opciones por un factor de al menos tres en cada etapa.
Me refiero a un posible (suma,producto) como $point$.
Deje $P$ ser un producto que en la mayoría de 1/3 de los posibles puntos de producto mayor que $P$ y en la mayoría de los 2/3 de los puntos posibles que tienen el producto a menos de $P$.
De los puntos con el producto a menos de $P$, vamos a $S$ ser la mediana de las sumas.
El sistema compara el verdadero suma y el producto a S y P, y se reduce el conjunto de puntos posibles para un conjunto de no más de 1/3 de lo que era.
Este método toma en la mayoría de las $\log_3{N\choose2}$ conjeturas.
