1.
2.
3.
Figura 19.1
Típico jogo para um conjunto de quatro elementos.A aresta {x,y} não está presente.
Se X for qualquer subconjunto da posição atual do jogo que contenha x, e se x for então
substituído por y, o subconjunto resultante também será um subconjunto da posição
atual do jogo.
Se Y for qualquer subconjunto da posição atual do jogo que contenha y, e se y for então
substituído por x, o subconjunto resultante também será um subconjunto da posição
atual do jogo.Assim, podemos remover os vértices x e y, com todos os simplexos que os contêm, sem
alterar o vencedor (contanto que os jogadores utilizem a melhor estratégia disponível).
Utilizando essa técnica, a prova de que, usando a estratégia ideal, Bruno sempre poderá vencer
o Roubo de Subconjuntos para n = 5 ou 6 se torna muito mais simples, e leva apenas alguns
minutos de análise.
De volta à minha pergunta sobre a estratégia do “complemento”. Quando n = 4, Alice pode
começar com um 0-simplexo (vértice), um 1-simplexo (aresta) ou um 2-simplexo (face
triangular). Se ela escolher um vértice e Bruno escolher o complemento, então o jogo será
reduzido ao caso n = 3, e Bruno vence. Se ela escolher uma face triangular e Bruno escolher o
ponto complementar, o jogo será novamente reduzido ao caso n = 3.
Mas o que ocorre se Alice escolher uma aresta (que, usando números, podemos presumir
que seja {1,2}) e Bruno escolher a aresta complementar {3,4}? A Figura 19.2 mostra que,
mais adiante, Bruno não poderá escolher um subconjunto complementar, porque tal
subconjunto não será um simplexo. Portanto, a estratégia “complementar” falha, pois não
especifica uma jogada permitida. No entanto, utilizando uma estratégia adequada, Bruno ainda
vence quando n = 4. Christiansen e Tilford conjecturaram que, para todo n, a resposta correta