El partido se puede ganar si y sólo si $n \neq k$

Question

Entero $n$ y $k$ con $n \ge k \ge 2$ . Juegas la siguiente partida contra un mago malvado.

El asistente ha $2n$ tarjetas; para cada $i = 1, \ldots, n$ hay dos tarjetas etiquetadas $i$ . Inicialmente, el mago coloca todas las cartas boca abajo en una fila, en orden desconocido.

Puedes realizar repetidamente movimientos de la siguiente forma: señalas cualquier $k$ de las tarjetas. A continuación, el mago pone esas cartas boca arriba. Si dos de las cartas coinciden, el juego termina y ganas. En caso contrario, debe mirar hacia otro lado mientras el mago cambia arbitrariamente las cartas. $k$ cartas elegidas y luego las vuelve a poner boca abajo. A continuación, vuelve a ser tu turno.

Decimos que este juego es ganable si existe algún número entero positivo $m$ y alguna estrategia que garantice ganar como máximo en $m$ se mueve, no importa cómo responda el mago.

Demostrar que se puede ganar el partido si y sólo si $n \neq k$ .

Answer 1

$\textbf{Winnable for } k<n:\quad$ En el paso $l$ , elige las cartas en posiciones $l,l+1,\ldots,l+k$ . Comparación de los $k-1$ tarjetas que se ven en las posiciones $l,l+1,\ldots,l+k-1$ con las que has visto en el paso anterior, puedes concluir qué carta está en la posición $l-1$ . (Obviamente, esto sólo se aplica a partir del paso $2$ ). En $n+2$ pasos para saber con certeza qué cartas están en las posiciones $1,2,\ldots,n+1$ . Dos de ellos deben coincidir, simplemente elígelos y $k-2$ otros arbitrarios.

Edición: El argumento de la no ganabilidad de $n=k$ fue un poco descuidado...

Answer 2

Supongo que por "permuta arbitraria de los $k$ cartas elegidas" quiere decir que el $k$ las cartas elegidas se colocan en sus posiciones originales pero en un orden diferente; es decir, de $\{1, 2, 3, 4, 5, \dotsc\}$ si $\{2, 3, 5\}$ entonces una colocación válida sería $\{1, 3, 5, 4, 2, \dotsc\}$ pero no $\{2, 3, 1, 4, 5\}$ . Además, supongo que ninguna carta se coloca en la misma posición (las cartas están trastornadas). El resto de esta respuesta se basa en estas suposiciones, por lo que le ruego que me aclare si son incorrectas.

Elige las tarjetas en los índices $1, 2, \dotsc, k$ y memorizar sus valores. Ahora elige las cartas en los índices $2, 3, \dotsc, k+1$ . Habrá exactamente un valor que haya aparecido en la primera elección, pero que no haya aparecido en la primera $k-1$ tarjetas de la segunda opción debido a la condición de enajenación. Ahora sabemos que ese valor está presente en el índice 1.

A continuación, elija las tarjetas en los índices $3, 4, \dotsc, k+2$ y por el argumento anterior, conocemos también el valor presente en el índice 2. Continúe este procedimiento hasta que conozcamos los valores de los primeros $2n - k$ índices. Si $2n - k > n \iff n > k$ entonces debe haber dos índices con el mismo valor en ellas: y como conocemos los valores específicamente, podemos elegir cualquiera $k$ tarjetas que contengan esas dos y ya está. Puesto que se da que $n \geq k$ es cierto que $n = k$ ou $n > k$ en este último caso, tenemos una estrategia ganadora que toma exactamente $n - k + 2$ pasos (¡cuéntalos!).

En el primer caso $n = k$ No puedo probar que no exista una estrategia ganadora, pero he hecho estas observaciones: la estrategia anterior definitivamente no funciona, y es posible que el mago haga "ingeniería inversa" de sus permutaciones (es decir, no permutarlas realmente hasta después de que hayas hecho tu elección mientras sigues las reglas, lo que equivale a un caso de no trampas si lo piensas) para que tu elección no contenga cartas iguales. Este método de ingeniería inversa no funciona para la estrategia anterior porque en cada paso, la permutación elegida no importa a la hora de decidir el siguiente paso.

Answer 3

Dos respuestas ya han dado una estrategia ganadora para $n\gt k$ .

Para $n=k$ en cada paso ganamos a menos que elijamos un conjunto completo de $n$ números diferentes. Los otros $n$ también son todos diferentes, por lo que cualquier subconjunto que elijamos de ellos en el siguiente paso, no contendrá un par, y no importa lo que sepamos acerca de estos números, no hay manera de evitar que los números restantes, que tienen que ser elegidos de los que se acaban de barajar, sean exactamente los que faltan para un conjunto completo de $n$ números diferentes. Dado que esto es cierto en cada paso, ningún paso es seguro de ganar, por lo que en este caso el juego no es ganable.