Este jogo termina?

12

Considere o seguinte jogo de cartas (conhecido na Itália como "Cavacamicia", que pode ser traduzido como "camisa de tiras"):

Dois jogadores dividem aleatoriamente em dois baralhos um baralho de cartas padrão. Cada jogador recebe um baralho.

Os jogadores alternam colocando na pilha a próxima carta do baralho.

Se um jogador (A) coloca uma carta especial, ou seja, I, II ou III, o outro jogador (B) deve colocar consecutivamente o número correspondente de cartas.

  • Se, ao fazer isso, B coloca uma carta especial, a ação é revertida e assim por diante; caso contrário, se B colocar o número correspondente de cartas, mas nenhuma carta especial, A coleta todas as cartas que foram colocadas e as adiciona ao seu baralho. A então reinicia o jogo colocando uma carta no chão.

O primeiro jogador a ficar sem cartas perde o jogo.

Nota: O resultado do jogo depende exclusivamente da partição inicial do baralho. (O que pode tornar este jogo um pouco inútil ;-)

Pergunta: Este jogo sempre termina? E se generalizarmos este jogo e dermos duas sequências de cartas a cada jogador?

Manu
fonte
4
Um jogo semelhante é o Mendigo-Meu-Vizinho ; jogado com um baralho de 52 cartas (A, J, Q, K são as penalidades). Também é conhecido como Strip Jack Naked ou Beat Your Neighbor Out of Doors e, de acordo com a Wikipedia, é um problema em aberto se existe ou não um jogo que não termina.
Marzio De Biasi
(uma vez que sua longa abertura soa como uma pergunta do tcs.se para mim.) Conway sugere na 1ª página desse ref para tentar pesquisas no computador. tem alguém? parece que uma boa estratégia seria tentar decks pequenos e responder exaustivamente à pergunta e aumentar o tamanho do deck. se está sempre terminando para decks pequenos, provavelmente parece verdadeiro para decks de tamanho arbitrário (e talvez uma prova indutiva possa ser criada dessa maneira). uma questão relacionada, há algum jogo de cartas que tenha sido provado, às vezes, não-determinante? presumivelmente, eles são bastante raros, porque a maioria dos jogos é baseada em alguém que acaba vencendo!
vzn
@ MarzioDeBiasi obrigado pelo link, é o mesmo jogo. Não vejo indecidibilidade porque, dado dois baralhos finitos, se o jogo termina é obviamente decidível.
Manu
@EmanueleViola: você está certo, se a mesma configuração de deck aparecer duas vezes, o jogo nunca terminará! Eu apaguei o comentário.
Marzio De Biasi
Este é o parafuso de rato egípcio, mas sem o tapa!
Argentpepper

Respostas:

10

Sobre Mendigo-Meu-Vizinho

Paulhus (1, p.164) escreveu em 1999:

CD2(C)

Mas Conway et al. (2, p.892) escreveu em 2006:

Strip-Jack-Naked, ou Mendigo-Meu-Vizinho ** 1

Outro problema que levou quase 47 anos para resolver diz respeito a esse velho jogo infantil. Cada um dos dois jogadores começa com cerca da metade das cartas (mantidas com a face para baixo), que alternadamente se transformam em uma pilha de face para cima na mesa, até que um deles (que agora é o "comandante") lide pela primeira vez uma das "cartas de comando" (Valete, Dama, Rei ou Ás).

Depois que uma delas é distribuída, o outro jogador (agora "o respondedor") vira as cartas continuamente até SEMPRE. ** 2, uma nova carta de comando aparece (quando os jogadores mudam de função ** 3) ou respectivamente 1, 2, 3 ou 4 cartas não-comandantes foram entregues. Neste último caso, o comandante vira a pilha e a prende ao fundo da mão. O respondente começa a formação de uma nova pilha virando a próxima carta e o jogo continua como antes.

Um jogador que adquire todas as cartas é o vencedor e, em jogos reais, parece que alguém sempre vence. A interessante questão matemática, colocada por um de nós há muitos anos, era "é realmente verdade que o jogo sempre acaba?" Marc Paulhus encontrou recentemente a resposta como "não!". Cerca de 1 em 150.000 jogos (jogados com as 52 cartas habituais) dura para sempre.

Estamos bastante confiantes de que ninguém jogou o jogo dessa maneira várias vezes; portanto, a chance (com embaralhamento aleatório) de experimentar um jogo que não termina na vida inteira deve ser muito pequena.

Com a mesma certeza, no entanto, o número total de vezes que esse jogo foi jogado pelas crianças do mundo ** 4 deve ser significativamente maior que 150.000, então muitas delas serão teoricamente não-terminativas. Imaginamos, no entanto, que na prática a maioria deles realmente terminou porque alguém cometeu um erro.

Infelizmente não consegui encontrar em (2) nenhuma referência à descoberta de Paulhus ... Adoraria ver uma sequência de cartas que oferecem um jogo sem fim para dizer que o problema está resolvido.

Em 2013, Lakshtanov e Aleksenko (3) escreveram:

Para jogos de cartas do tipo Mendigo-Meu-Vizinho, comprovamos a finitude da expectativa matemática da duração do jogo, nas condições em que um jogador para jogar a primeira carta é escolhido aleatoriamente e que as cartas em uma pilha são embaralhadas antes de serem colocadas na mesa. área coberta. O resultado também é válido para modificações de tipo geral das regras do jogo. Em outras palavras, mostramos que o gráfico da cadeia de Markov para o jogo Mendigo-Meu-Vizinho é absorvente; ou seja, de qualquer vértice, há pelo menos um caminho que leva ao final do jogo.

mas as regras deles não são as que eu segui quando joguei quando criança ;-)

Que eu saiba, o jogo Beggar-my-Neighbor mais longo foi encontrado em 2014 por William Rucklidge com 7960 cartões :

1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK

Em relação à Cavacamicia

Eu geralmente jogava com um baralho de 40 cartas, simulações com meio baralho (apenas 20 cartas) oferecem 16 jogos sem encerramento, em um total de 3.448.400 jogos.

Bibliografia

(1) PAULHUS, Marc M. Mendigo, meu vizinho. American Mathematics Monthly , 1999, 162-165. http://www.jstor.org/stable/2589054

(2) BERLEKAMP, Elwyn R .; CONWAY, John H .; GUY, Richard K. Vencer maneiras de suas peças matemáticas, volume 4. AMC, 2003, 10: 12. http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays -volume-4

(3) LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Finitude no jogo de cartas Mendigo-Meu-Vizinho. Problemas de transmissão de informações , 2013, 49.2: 163-166. http://dx.doi.org/10.1134/S0032946013020051

Alessandro Jacopson
fonte