Intercambio de la tarjeta más grande del th de $i$ entre $2$ manos de tarjetas de

Question

Introducción a "el juego"

Hay $2$ jugadores y $2n$ tarjetas, con la etiqueta $1, 1, 2, 2, 3, 3, 4, 4, \dots, n, n$. ($2$ de cada tarjeta de$1$$n$)

En primer lugar, el $2n$ de los jugadores son cada determinado $n$ tarjetas al azar. Más específicamente, un ordenamiento al azar de la $2n$ tarjetas se logra y el primer jugador obtiene el primer lugar en $n$ tarjetas, el segundo jugador obtiene de la otra $n$ tarjetas. Podemos asumir que cada jugador puede ver todas las cartas.

En cada turno, cada jugador va a ordenar su mano de cartas. La etiqueta de los naipes en las manos $a_1, a_2, a_3,\dots, a_n, b_1, b_2, b_3,\dots, b_n$.

Los jugadores encontrar un par de tarjetas de $a_i\neq b_i$. Luego que el intercambio de las tarjetas de $a_i$$b_i$. Después de lo cual, el turno termina.

Claramente si $a_i=b_i$ todos los $i$,$a_i=b_i=i$, y el "juego" termina.

Ejemplo

Deje $n=4$. Llamamos a la $2$ jugadores de $A, B$. En el inicio del juego, que reciben:

$A: 1, 1, 2, 2$

$B: 3, 3, 4, 4$

Turno 1: de Que decidan cambiar la tarjeta por primera vez.

$A: \color{red}{3}, 1, 2, 2$

$B: \color{red}{1}, 3, 4, 4$

Antes de la segunda vuelta comienza, ordenar sus tarjetas.

$A: 1, 2, 2, 3$

$B: 1, 3, 4, 4$

Vuelta 2: Esta vez, deciden cambiar la tarjeta de tercero. No se pueden intercambiar la primera tarjeta con los números de la primera tarjeta son los mismos.

$A: 1, 2, \color{red}{4}, 3$

$B: 1, 3, \color{red}{2}, 4$

Que ordenar sus tarjetas.

$A: 1, 2, 3, 4$

$B: 1, 2, 3, 4$

El juego termina cuando los jugadores de ambos ha $1, 2, 3, 4$. Este juego termina en $2$ turnos.

Preguntas acerca de este "juego"

Va a terminar? (La respuesta es sí, y una idea de un límite basado en el monovariant se añadirá como una auto-respuesta.)

En cuántos se mueve (en la mayoría) tarda un $2n$ juego de cartas para terminar? Lo que los acuerdos que hará que se tome tanto tiempo para terminar?

Suponiendo que el jugador tiene que escoger el lado de la tarjeta para el intercambio de azar (de entre todos los posibles movimientos, elija un movimiento válido, cada movimiento válido, con igual probabilidad), lo que se espera que el número de movimientos para el juego para terminar?

Ideas acerca de la pregunta:

Como sugiere hardmath:

Si hemos de limitar a los jugadores a tomar la carta más baja que las obras o la carta más alta que funciona, el juego será definitivamente final en la mayoría de los $n-1$ turnos. Ambos casos son simétricos, por lo tanto, trabajar en la más alta.

Caso Base: si $n=1$, no se mueve tiene que ser hecho. De lo contrario, $n>1$.

Ahora procedemos en el paso inductivo. Supongamos que la más alta de las tarjetas de los jugadores son diferentes. Si son iguales, se elimina, la reducción de la $n-1$ de los casos, lo que se puede hacer en la mayoría de los $n-2$ se mueve. De lo contrario, un jugador que tiene la carta más alta. Cuando el movimiento se hace, una copia de la carta más alta se da para el otro jugador. Ahora, ambos jugadores tiene la carta más alta, y puede ser eliminada. En total, hay $1+(n-2)=n-1$ se mueve por este.

A partir de esto, podemos obtener que, en promedio, el juego termina en $O(n^2)$ gira, ya que se necesita (en promedio) $O(n)$ vueltas por la carta más alta para ser intercambiados.

Código (para referencia):

Me encontré con una simulación de Monte Carlo de juegos de azar. Una simulación de $1000$ juegos de $1000$ tarjetas dio un promedio de número de intercambios de $1310.703$.

El código de C++ para la referencia:

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
int K;
int maxCounter = 0;
int sumCounter = 0;
int counter;
int arr[999999];
/** Results:
(X cards, 10^6 rounds)
1 -> 0 0
2 -> 1 0.334546 (guess: 1/3)
3 -> 2 0.733746
4 -> 3 1.180559
5 -> 5 1.667006 (guess: 5/3)
6 -> 6 2.179321
7 -> 8 2.721661
8 -> 9 3.283566
9 -> 10 3.867299
10 -> 12 4.471352
Other things I tried: (cards, rounds)
100 1000 -> 143 84.411
200 1000 -> 307 197.332
300 1000 -> 503 319.691
500 1000 -> 960 580.373
1000 1000 -> 1910 1310.703
**/
int main(void) {
    srand(23);
    printf("Number of cards: ");
    scanf("%d", &N);
    for (int i=0;i<N;i++) {
        arr[i] = arr[i+N] = i;
    }
    printf("Number of rounds: ");
    scanf("%d", &K);
    for (int j=0;j<K;j++) {
        random_shuffle(arr, arr+2*N);
        counter = 0;
        while (counter>=0) {
            sort(arr, arr+N);
            sort(arr+N, arr+2*N);
            int pass = 1;
            for (int i=0;i<N;i++) {
                if (arr[i] != arr[i+N]) {
                    pass = 0;
                    break;
                }
            }
            if (pass) break;
            counter++;
            int theMove = rand()%N;
            while (arr[theMove] == arr[theMove+N]) theMove = rand()%N;
            int temp = arr[theMove];
            arr[theMove] = arr[theMove+N];
            arr[theMove+N] = temp;
        }
        //printf("%d ", counter);
        maxCounter = max(maxCounter, counter);
        sumCounter += counter;
        if (j%(K/100) == 0) printf("Done: %d\n", j);
    }
    printf("Maximum: %d\nAverage: %lf\n", maxCounter, sumCounter/(double)K);
    return 0;
}

Los resultados del código:

El número promedio de movimientos parecen crecer más rápido de lo $O(n)$.

Answer 1

Aquí es un plan de con $O(n\log n)$ se mueve.
Empezar con $n=2^{m}-1$. Deja que una mano se $1,1,2,2,...,2^{m-1}$, por lo que la otra parte comienza con el resto de $2^{m-1}$.
En $(n-1)/2=2^{m-1}-1$ se mueve, cambiar las tarjetas en el medio de la fila cada vez.
Usted va a terminar con ambas tarjetas etiquetadas $2^{m-1}$ en el medio, con la mayor de las tarjetas formando una estructura similar a la anterior $2^{m-1}$ y la más baja de las tarjetas formando una estructura similar a la de abajo $2^{m-1}$. Así que una mano tiene el cuartil más bajo de tarjetas, y el otro lado tiene el cuartil más alto de tarjetas. Por ejemplo, usted tendría $1,1,2,4,5,5,6$ en una mano y $2,3,3,4,6,7,7$ en el otro.
A continuación, repita el proceso, para la mayor de las tarjetas y de las cartas más bajas. El número total de movimientos es $M(m)=2M(m-1)+2^{m-1}-1$.
2 movimientos son posibles para $n=3$, lo $M(m)=(m-\frac32)2^{m-1}+1$$n=2^m-1$.

Answer 2

Esta no es una respuesta completa a la pregunta todavía.

El monovariant $\sum i(a_i+b_i)$ fue sugerido por Michael en los comentarios.

Cuando el intercambio se realiza, el monovariant sigue siendo el mismo.

El monovariant aumentará cuando uno de los $2$ listas de convertirse en sin clasificar después del intercambio. Tratamos de probar que esto es el caso.

Partimos en $2$ de los casos:

Caso 1: $|a_i-b_i|>1$

Se considera que las tarjetas etiquetadas $a_i+1$ están colocados. Tampoco existen como tarjetas de $a_j$ donde $j>i$ o $b_k$ donde $k<i$. En tanto subcases en el caso 1, habrá un reordenamiento ya que las manos no están ordenadas después del intercambio.

Caso 2: $|a_i-b_i|=1$

Sin pérdida de generalidad, vamos a $a_i-b_i=1$. A continuación, consideramos que las tarjetas etiquetadas $a_i$$b_i$. Para mayor comodidad, la etiqueta de las tarjetas $x$, $x+1$.

$\begin{matrix} A:&\dots&x+1&\dots\\ B:&\dots&x&\dots \end{de la matriz}$

Ahora tenemos en cuenta las posiciones de los otros $2$ tarjetas de etiquetado $x$, $x+1$.

Teniendo en cuenta todas las tarjetas etiquetadas $1, 2, 3,\dots, x-1$, hay un número de dichas tarjetas. Todas estas cartas deben aparecer antes de que los naipes $x, x+1$ en ambas listas.

Para el sin colocar $x, x+1$, si sólo uno aparece antes de la $i$th posición, entonces hay un número impar de posiciones para un número par de cartas, lo cual es imposible.

Por lo tanto ambos aparecen antes de la $i$th posición o después de la $i$th posición.

Hay 2 casos (azul: tarjetas de intercambio, rojo: después de la permuta):

$\begin{matrix} A:&\dots&\color{blue}{x+1}&x+1&\dots\\ B:&\dots&\color{blue}{x}&x&\dots \end{de la matriz}\rightarrow\begin{matrix} A:&\dots&\color{red}{x}&x+1&\dots\\ B:&\dots&\color{red}{x+1}&x&\dots \end{de la matriz}$

$\begin{matrix} A:&\dots&x+1&\color{blue}{x+1}&\dots\\ B:&\dots&x&\color{blue}{x}&\dots \end{de la matriz}\rightarrow\begin{matrix} A:&\dots&x+1&\color{red}{x}&\dots\\ B:&\dots&x&\color{red}{x+1}&\dots \end{de la matriz}$

Agotador ambos casos demuestra la monovariant.

Por lo tanto, se ha demostrado que este termina.

El valor final de la monovariant es $\sum i(2i) = \frac{n(n+1)(2n+1)}{3}$.

El valor inicial de la monovariant es, al menos, $\sum 2i(n+1-i)$ (el 2 manos se $n, n-1, n-2, \dots, 3, 2, 1$, que es mínimo, por Reordenación de la Desigualdad).