Intercambiar la tercera carta más grande entre 222 manos de cartas

Introducción al "juego"

Hay$2$jugadores y$2n$tarjetas, etiquetadas$1, 1, 2, 2, 3, 3, 4, 4, \dots, n, n$. ($2$de cada carta de$1$a$n$)

En primer lugar, el$2n$cada jugador recibe$n$cartas al azar. Más específicamente, un orden aleatorio de los$2n$se consiguen cartas y el primer jugador obtiene la primera$n$cartas, el segundo jugador recibe el otro$n$tarjetas Podemos suponer que cada jugador puede ver todas las cartas.

En cada turno, cada jugador ordenará su mano de cartas. Etiqueta las cartas en las manos.$a_1, a_2, a_3,\dots, a_n, b_1, b_2, b_3,\dots, b_n$.

Los jugadores encuentran un par de cartas.$a_i\neq b_i$. Luego intercambian las cartas.$a_i$y$b_i$. Después de lo cual, el turno termina.

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

Ejemplo

Dejar$n=4$. llamamos al$2$jugadores$A, B$. Al comienzo del juego, reciben:

$A: 1, 1, 2, 2$

$B: 3, 3, 4, 4$

Turno 1: Deciden intercambiar la primera carta.

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

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

Antes de que comience el segundo turno, ordenan sus cartas.

$A: 1, 2, 2, 3$

$B: 1, 3, 4, 4$

Turno 2: Esta vez, deciden intercambiar la tercera carta. No pueden intercambiar la primera tarjeta ya que los números en la primera tarjeta son los mismos.

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

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

Clasifican sus tarjetas.

$A: 1, 2, 3, 4$

$B: 1, 2, 3, 4$

El "juego" termina cuando ambos jugadores tienen$1, 2, 3, 4$. Este juego termina en$2$vueltas

Preguntas sobre este "juego"

¿Terminará? (La respuesta es sí, y se agregará una idea de un límite basado en la monovariante como respuesta).

¿En cuántos movimientos (como máximo) se necesita para un$2n$juego de cartas para terminar? ¿Qué arreglos harán que tarde tanto en terminar?

Suponiendo que los jugadores eligen la siguiente carta para intercambiar al azar (entre todos los movimientos posibles, elija un movimiento válido, cada movimiento válido con la misma probabilidad), ¿cuál es el número esperado de movimientos para que termine el juego?

Ideas sobre la pregunta:

Como sugiere hardmath:

Si restringimos a los jugadores a tomar la carta más baja que funcione o la carta más alta que funcione, el juego definitivamente terminará como máximo$n-1$vueltas Ambos casos son simétricos, por lo que trabajamos en lo más alto.

Caso base: si$n=1$, no hay que hacer ningún movimiento. De lo contrario,$n>1$.

Procedemos ahora al paso inductivo. Supongamos que las cartas más altas de los jugadores son diferentes. Si son iguales, las borramos, reduciéndolas a la$n-1$caso, que se puede hacer como máximo$n-2$se mueve De lo contrario, un jugador tiene la carta más alta. Cuando se hace el movimiento, se entrega una copia de la carta más alta al otro jugador. Ahora, ambos jugadores tienen la carta más alta y se puede eliminar. En total, hay$1+(n-2)=n-1$se mueve para esto.

De esto, podemos obtener que en promedio, el juego termina en$O(n^2)$vueltas, ya que toma (en promedio)$O(n)$turnos para intercambiar la carta más alta.

Código (para referencia):

Ejecuté una simulación Monte Carlo de juegos aleatorios. una simulación de$1000$juegos de$1000$tarjetas dieron un número promedio de intercambios de$1310.703$.

Código C++ para 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;
}

Resultados del código:

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