On an Erdős-Szekeres Game

Este artigo analisa um jogo de permutações de dois jogadores inspirado no Teorema de Erdős-Szekeres, determinando o vencedor e fornecendo uma estratégia vencedora quando $a \geq b$ e $b \in \{2, 3, 4, 5\}$.

O essencial

Imagine que você e um amigo estão jogando um jogo de "construção de torres" com cartas numeradas, mas com uma regra muito específica: quem for o primeiro a criar uma torre muito alta (em ordem crescente) ou uma pilha muito profunda (em ordem decrescente), perde.

Este é o cerne do artigo de Lara Pudwell, que transforma um teorema matemático famoso (o Teorema de Erdős-Szekeres) em um jogo de estratégia para dois jogadores. Vamos descomplicar isso usando analogias do dia a dia.

1. O Cenário: O Jogo das Cartas

Imagine que vocês têm um baralho com números de 1 a $N$. Vocês tiram as cartas uma por uma e as colocam em uma fila na mesa.

• O Objetivo: Evitar que apareça uma sequência de $A$ cartas subindo (como 1, 2, 3, 4...) ou uma sequência de $B$ cartas descendo (como 10, 9, 8, 7...).
• A Regra de Perda: Assim que alguém colocar uma carta que completa uma dessas sequências proibidas, essa pessoa perde o jogo (na versão "misère" que o artigo analisa).

O teorema antigo dizia: "Se você tiver cartas suficientes, é impossível não formar uma dessas sequências". O jogo pergunta: "Quem vai ser o infeliz que vai completar a sequência primeiro?"

2. O Truque do Autor: O Tabuleiro de "Sombra"

A autora não olha para as cartas em si, mas sim para um tabuleiro de quadradinhos (como um jogo da velha gigante).

• A Analogia da Sombra: Imagine que cada carta que vocês jogam projeta uma "sombra" em um gráfico.
  • Se a carta é alta na sequência (muitas cartas subindo antes dela), a sombra vai para a direita.
  • Se a carta é baixa na sequência (muitas cartas descendo antes dela), a sombra vai para cima.
• O Jogo Real: Em vez de pensar em números, os jogadores estão pintando quadradinhos nesse tabuleiro.
  • Você só pode pintar um quadradinho se ele estiver "encostado" na área já pintada (como se estivesse expandindo uma mancha de tinta).
  • O jogo termina quando alguém pinta o quadradinho no canto inferior direito. Quem pinta esse último quadradinho vence, porque força o oponente a fazer o movimento final que cria a sequência proibida.

É como se vocês estivessem construindo um muro. Quem coloca a última pedra que fecha o muro perde (porque o muro está completo e o oponente não tem mais para onde ir).

3. A Estratégia: Quem Ganha?

O artigo descobre quem ganha o jogo dependendo de dois números:

• $A$: O tamanho da sequência crescente proibida.
• $B$: O tamanho da sequência decrescente proibida.

A autora foca em casos onde $A$ é maior ou igual a $B$, e $B$ é pequeno (2, 3, 4 ou 5).

• Caso $B = 2$ (Apenas 2 cartas descendo): É como um jogo de "par ou ímpar". Se o número total de cartas permitidas for par, o segundo jogador ganha. Se for ímpar, o primeiro ganha. É simples, como jogar "Pedra, Papel e Tesoura" onde a sorte do número define o vencedor.
• Caso $B = 3, 4, 5$ (Sequências um pouco maiores): Aqui é onde a mágica acontece. A autora descobriu que o Primeiro Jogador tem sempre uma estratégia vencedora, não importa o tamanho de $A$ (desde que seja grande o suficiente).
  • Como? O primeiro jogador usa um "espelho" ou um "sistema de compensação". Se o segundo jogador pinta um quadradinho de um jeito, o primeiro jogador pinta um quadradinho específico que mantém o tabuleiro em um "estado seguro". É como se o primeiro jogador fosse um maestro que, não importa qual nota o segundo toque, sempre toca a nota seguinte que mantém a música harmoniosa e segura, até que o segundo jogador seja forçado a tocar a nota que estraga tudo.

4. Por que isso é importante?

O artigo é importante porque:

1. Simplifica o Complexo: Transforma um problema abstrato de teoria dos números em um jogo visual de pintar quadradinhos.
2. Descobre Padrões: Mostra que, mesmo em jogos complexos, existem regras ocultas (estratégias) que garantem a vitória para quem conhece o "mapa".
3. Expande o Conhecimento: Antes, só sabíamos quem ganhava em casos muito pequenos. Agora, temos a estratégia para casos onde a sequência decrescente tem até 5 cartas, e a sequência crescente pode ser gigante.

Resumo em uma frase

O artigo mostra que, num jogo onde dois jogadores tentam evitar criar sequências de números ordenados, o primeiro jogador pode sempre vencer (em certos cenários) usando uma estratégia de "pintura de tabuleiro" que mantém o jogo em um estado seguro, forçando o oponente a cometer o erro final.

É como se o primeiro jogador soubesse exatamente onde colocar cada tijolo para que o segundo jogador, inevitavelmente, tenha que colocar o último tijolo e derrubar a parede.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "On an Erdős-Szekeres Game" de Lara Pudwell, apresentado em português:

Resumo Técnico: Sobre um Jogo de Erdős-Szekeres

1. O Problema
O artigo investiga uma versão competitiva de dois jogadores baseada no famoso Teorema de Erdős-Szekeres (1935). O teorema afirma que qualquer permutação de comprimento $n \ge (a-1)(b-1) + 1$ contém necessariamente uma subsequência crescente de comprimento $a$ ou uma subsequência decrescente de comprimento $b$.

O jogo proposto funciona da seguinte maneira:

• Dois jogadores alternam turnos selecionando números de um conjunto de inteiros, construindo uma permutação incrementalmente.
• O jogo termina quando um jogador completa involuntariamente uma subsequência crescente de comprimento $a$ ($I_a$) ou uma subsequência decrescente de comprimento $b$ ($J_b$).
• O foco deste trabalho é a variante misère (ou "perdedor vence" no sentido inverso): o primeiro jogador que completa tal padrão perde o jogo.
• O objetivo é determinar o vencedor e fornecer estratégias vencedoras para parâmetros $a \ge b$ e $b \in \{2, 3, 4, 5\}$.

2. Metodologia
A principal inovação metodológica do artigo é a reformulação do jogo de permutações em um jogo de sombreamento em uma grade bidimensional. Inspirado na prova de Seidenberg (1959) do teorema original, o autor mapeia o estado do jogo para uma grade de $(b-1)$ linhas por $(a-1)$ colunas.

• Representação em Grade: Cada célula $(c, r)$ na grade representa o par ordenado $(c, r)$, onde $c$ é o comprimento da maior subsequência crescente terminando no último elemento adicionado e $r$ é o comprimento da maior subsequência decrescente terminando no mesmo elemento.
• Mecânica do Jogo:
  • O tabuleiro começa vazio.
  • Os jogadores "sombream" células. Uma célula é sombreada se corresponder ao par $(c, r)$ do próximo elemento da permutação.
  • Regra de eliminação: Se a célula $(c, r)$ é sombreada, todas as células $(c', r')$ onde $c' \le c$ e $r' \le r$ tornam-se "eliminadas" (não podem ser sombreadas no futuro).
  • O jogo é jogado na fronteira entre as células eliminadas e as abertas.
  • O jogador que sombrea a célula no canto inferior direito $(a-1, b-1)$ vence, pois isso significa que o tabuleiro está totalmente eliminado, forçando o próximo jogador a criar um padrão proibido.
• Análise Computacional e Combinatória: Para casos complexos ($b=5$), o autor utilizou buscas computacionais para classificar estados do jogo como posições de vitória para o próximo jogador (Classe N) ou derrota (Classe P), identificando padrões que foram generalizados em estratégias manuais.

3. Contribuições Principais e Resultados

O artigo fornece estratégias vencedoras completas para o primeiro jogador (Jogador 1) na variante misère para os seguintes casos, onde $a \ge b$:

• Caso $b=2$:
  • O tabuleiro é uma linha única. O vencedor é determinado pela paridade de $a$. Se $a$ for par, o Jogador 1 vence; se $a$ for ímpar, o Jogador 2 vence.
• Caso $b=3$:
  • O Jogador 1 possui uma estratégia vencedora para qualquer $a \ge 3$. A estratégia envolve manter um equilíbrio específico entre as células sombreadas nas duas linhas, forçando o oponente a completar o padrão.
• Caso $b=4$:
  • O Jogador 1 possui uma estratégia vencedora para qualquer $a \ge 4$. A estratégia é descrita em termos de formas de sombreamento (padrões de células eliminadas nas três linhas), onde o Jogador 1 responde aos movimentos do oponente para manter o tabuleiro em duas configurações específicas de "estado seguro".
• Caso $b=5$ (Contribuição Original):
  • Este é o resultado mais significativo do artigo, estendendo o conhecimento além do que foi feito por Albert et al. (2009).
  • O Jogador 1 possui uma estratégia vencedora para qualquer $a \ge 5$.
  • A estratégia é dividida em três fases: abertura, meio-jogo e fim de jogo.
  • O autor define um conjunto de estados de meio-jogo ($\mathcal{S}$) compostos por 7 configurações específicas de células eliminadas. O Jogador 1 garante que, após cada um de seus turnos, o tabuleiro retorne a um estado em $\mathcal{S}$, independentemente do movimento do Jogador 2.
  • O artigo demonstra que é possível navegar de qualquer estado em $\mathcal{S}$ para um conjunto de estados de fim de jogo ($\mathcal{E}$), onde o Jogador 1 pode aplicar uma resposta "título por título" (tit-for-tat) para forçar a vitória.

4. Discussão sobre o Jogo Normal (Normal Play)
O artigo também discute brevemente a variante de "jogo normal" (onde quem completa o padrão vence).

• O autor observa que o jogo normal é essencialmente equivalente ao jogo misère, mas jogado em um tabuleiro reduzido de $(b-2) \times (a-2)$.
• Isso confirma a conjectura de que o Jogador 1 vence no jogo normal para $4 \le b \le 6$.

5. Significado e Impacto

• Generalização de Estratégias: O trabalho resolve casos específicos ($b=4$ e $b=5$) que eram considerados computacionalmente proibitivos para análise pura de árvores de decisão devido ao crescimento exponencial dos estados.
• Nova Perspectiva Visual: A tradução do problema de permutações para o sombreamento de grades oferece uma ferramenta visual poderosa para analisar jogos combinatórios complexos, facilitando a identificação de invariantes e estratégias simétricas.
• Extensão de Resultados Anteriores: Enquanto trabalhos anteriores (como Harary, Sagan e West em 1983 e Albert et al. em 2009) focaram em análises computacionais limitadas ou no jogo em $\mathbb{Q}$, este artigo fornece estratégias explícitas e generalizáveis para $a$ arbitrariamente grande, desde que $a \ge b$.
• Análise de Complexidade: O artigo discute o número de movimentos necessários para vencer, mostrando que as estratégias otimizadas resultam em jogos significativamente mais curtos do que o limite superior teórico dado pelo Teorema de Erdős-Szekeres.

Em suma, o artigo estabelece uma nova estrutura geométrica para analisar jogos de permutação baseados em padrões, fornecendo soluções completas para uma classe de parâmetros anteriormente aberta e propondo direções futuras para $b \ge 6$.