juego de busqueda por permutacion

Question

juego de busqueda por permutacion

algoritmos
Matemáticas
combinatoria
combinatoria-teoria-de-juegos

Hans

Ordenar los números naturales $1$ a través de $n$ en un orden aleatorio (el orden es desconocido y tiene una distribución uniforme). Ahora haga una secuencia de conjeturas sobre qué número está en qué ranura, un número y una ranura a la vez. Se le dirá después de cada conjetura si es correcta o no. El juego termina cuando la orden del $n$ los números han sido determinados. Para el peor de los casos y el caso promedio, respectivamente, ¿hay alguna estrategia que requiera menos conjeturas que la eliminación trivial?

ferson2020

Parece que debido a la simetría, la estrategia óptima es adivinar aleatoriamente (sin adivinar números que ya se han encontrado, por supuesto). ¿Tiene alguna razón para sospechar que hay una mejor estrategia?

hmakholm sobra a Monica

@ferson2020: Desde una perspectiva matemática, la pregunta interesante es: ¿Podemos probar que no hay mejor estrategia? No puedo de inmediato, pero parece que debería haber algún argumento de amortización inteligente que muestre que uno siempre puede necesitar preguntar

n (n - 1) / 2

$n(n-1)/2$ preguntas en el peor de los casos, o tal vez simplemente algo

O (n^{2})

$O(n^2)$ .

ferson2020

Una vez más, argumentaría simetría. En cualquier etapa dada, tienes alguna permutación de

k < n

$k < n$ quedan cosas, y hay que elegir cuál está, sin pérdida de generalidad, en primera posición. Sería extraño pensar que podría haber algún sesgo debido a cualquier estrategia de que debería elegir uno de los elementos sobre los demás.

ferson2020

Curiosamente, creo que el valor esperado de las conjeturas correctas dadas

n

$n$ artículos es el

n

$n$ º parcial de la serie armónica:

\sum_{k = 1}^{n} \frac{1}{k}

$\displaystyle \sum_{k = 1}^n \frac{1}{k}$ , lo que significa que el valor esperado se aproxima al infinito cuando

n

$n$ aumenta

hmakholm sobra a Monica

@ ferson2020: Pero "sería extraño pensar" no es una prueba. A priori, tal vez podría haber alguna estrategia inteligente que obtenga alguna ventaja estratégica al pasar a preguntar sobre el espacio 2 antes de que sepa lo suficiente como para concluir algo definitivo sobre el espacio 1 ... entonces, en general, no puede reducir el trabajo más tarde a descubrir un permutación más pequeña de una pizarra limpia.

ferson2020

Está bien, pero argumentaría por inducción que cualquier estrategia en la que elijas un número al azar (que no se haya mostrado ya en un espacio diferente) es equivalente.

joriki

La pregunta no se puede responder en su forma actual porque no ha especificado los pagos del juego. Si los beneficios favorecen soluciones rápidas, existen estrategias óptimas no triviales. Por ejemplo, para

n = 3

$n=3$ , después de adivinar incorrectamente, digamos,

1

$1$ para la primera ranura, adivinar, digamos,

2

$2$ para la segunda ranura ofrece una

1

$1$ en

4

$4$ oportunidad de saber después

2

$2$ adivina que el arreglo es

321

$321$ si la conjetura resulta ser correcta. Por el contrario, hacer otra conjetura para el primer espacio seguramente conducirá a un total de tres conjeturas.

Hans

@joriki: edité la pregunta para especificar explícitamente el objetivo o la función de pago. ¿Que piensas ahora?

joriki

@ferson: Esto se llama el

n

$n$ -ésimo número armónico y a menudo denotado por

H_{n}

$H_n$ .

ferson2020

Vale interesante! Supuse que si adivinabas mal para un espacio, te decían que estabas equivocado al decirte cuál era la respuesta correcta. ¡Le daré una oportunidad a este problema actualizado!

Respuestas (1)

juego de busqueda por permutacion

Parece que debido a la simetría, la estrategia óptima es adivinar aleatoriamente (sin adivinar números que ya se han encontrado, por supuesto). ¿Tiene alguna razón para sospechar que hay una mejor estrategia?
@ferson2020: Desde una perspectiva matemática, la pregunta interesante es: ¿Podemos probar que no hay mejor estrategia? No puedo de inmediato, pero parece que debería haber algún argumento de amortización inteligente que muestre que uno siempre puede necesitar preguntar $n(n-1)/2$ preguntas en el peor de los casos, o tal vez simplemente algo $O(n^2)$ .
Una vez más, argumentaría simetría. En cualquier etapa dada, tienes alguna permutación de $k < n$ quedan cosas, y hay que elegir cuál está, sin pérdida de generalidad, en primera posición. Sería extraño pensar que podría haber algún sesgo debido a cualquier estrategia de que debería elegir uno de los elementos sobre los demás.
Curiosamente, creo que el valor esperado de las conjeturas correctas dadas $n$ artículos es el $n$ º parcial de la serie armónica: $\displaystyle \sum_{k = 1}^n \frac{1}{k}$ , lo que significa que el valor esperado se aproxima al infinito cuando $n$ aumenta
@ ferson2020: Pero "sería extraño pensar" no es una prueba. A priori, tal vez podría haber alguna estrategia inteligente que obtenga alguna ventaja estratégica al pasar a preguntar sobre el espacio 2 antes de que sepa lo suficiente como para concluir algo definitivo sobre el espacio 1 ... entonces, en general, no puede reducir el trabajo más tarde a descubrir un permutación más pequeña de una pizarra limpia.
Está bien, pero argumentaría por inducción que cualquier estrategia en la que elijas un número al azar (que no se haya mostrado ya en un espacio diferente) es equivalente.
La pregunta no se puede responder en su forma actual porque no ha especificado los pagos del juego. Si los beneficios favorecen soluciones rápidas, existen estrategias óptimas no triviales. Por ejemplo, para $n=3$ , después de adivinar incorrectamente, digamos, $1$ para la primera ranura, adivinar, digamos, $2$ para la segunda ranura ofrece una $1$ en $4$ oportunidad de saber después $2$ adivina que el arreglo es $321$ si la conjetura resulta ser correcta. Por el contrario, hacer otra conjetura para el primer espacio seguramente conducirá a un total de tres conjeturas.
@joriki: edité la pregunta para especificar explícitamente el objetivo o la función de pago. ¿Que piensas ahora?
@ferson: Esto se llama el $n$ -ésimo número armónico y a menudo denotado por $H_n$ .
Vale interesante! Supuse que si adivinabas mal para un espacio, te decían que estabas equivocado al decirte cuál era la respuesta correcta. ¡Le daré una oportunidad a este problema actualizado!

usuario96614 · Answer 1

No hay estrategia que cueste menos de $n(n-1)/2$ En el peor de los casos. Considere una estrategia (un menú de qué preguntas hacer en función del historial de respuestas anteriores). Considere un caso en el que todas las preguntas formuladas dan como resultado respuestas negativas (puede haber muchos de estos casos si la estrategia aleatoriza las preguntas). Supongamos que la estrategia concluye que la permutación es $P=(k_1,k_2,...,k_n)$ . es decir, el número $1$ está en la ranura $k_1$ , número $2$ en la ranura $k_2$ , ... y número $n$ en la ranura $k_n$ . Considere otra permutación $P'$ obtenido de $P$ intercambiando posiciones de números $i$ y $j$ . La única forma en que la estrategia podría haber determinado que la permutación es $P$ y no $P'$ es haciendo una de las siguientes dos preguntas: (1) ¿Es el número $i$ en la ranura $k_j$ ? o (2) es número $j$ en la ranura $k_i$ ? Así, para cada par $(i,j)$ , la estrategia debería haber formulado al menos una pregunta. Puesto que hay $n(n-1)/2$ pares, la estrategia debería haber preguntado al menos $n(n-1)/2$ preguntas.

¡Lindo! La idea clave aquí es que para una estrategia óptima siempre habrá casos en los que todas las respuestas sean "no", porque si no es así, una de las preguntas sería superflua.

juego de busqueda por permutacion

Hans

ferson2020

hmakholm sobra a Monica

ferson2020

ferson2020

hmakholm sobra a Monica

ferson2020

joriki

Hans

joriki

ferson2020

Respuestas (1)

usuario96614

hmakholm sobra a Monica

Fibonacci nim estrategias ganadoras en diferentes situaciones

¿Cuántos patrones únicos existen para una cuadrícula de 5x5 con caminos de espacios que se cruzan en 1 espacio y conducen a cada borde de la cuadrícula?

Contar estructuras multidimensionales (estados del juego Chomp)

Encontrar la estrategia ganadora en esta variación de chomp

Encuentra el número de Grundy de la posición inicial y haz el primer movimiento en una estrategia ganadora para el siguiente juego

¿Ganar un juego restringido de Nim?

Comprobación de Sudoku - sumas suficientes

Algoritmo para generar todas las combinaciones de lista de conjuntos con hasta un elemento por conjunto

Estrategia ganadora - variación de nim

Juego de mesa - estrategia ganadora