1. **Enunciado do problema:** Considere uma variação do jogo de Nim com $n$ cartas. Dois jogadores podem remover 1, 2 ou 3 cartas por vez. O jogador que remover a última carta perde. Queremos provar por indução completa que, se ambos jogam com a melhor estratégia, o primeiro jogador vence quando $n = 4j$, $4j + 2$ ou $4j + 3$ para qualquer inteiro não negativo $j$, e o segundo jogador vence quando $n = 4j + 1$. 2. **Definição do problema e estratégia:** Definimos $P(n)$ como a proposição "o primeiro jogador vence com $n$ cartas". 3. **Base da indução:** Para $j=0$: - $n=0$: jogo não começa, trivial. - $n=1$: $4(0)+1=1$, o segundo jogador vence (pois o primeiro é forçado a tirar a última carta e perder). - $n=2$: $4(0)+2=2$, o primeiro jogador vence. - $n=3$: $4(0)+3=3$, o primeiro jogador vence. - $n=4$: $4(1)=4$, o primeiro jogador vence. 4. **Hipótese de indução:** Suponha que para todos $k < n$, a proposição $P(k)$ é verdadeira. 5. **Passo indutivo:** Queremos provar $P(n)$. - Se $n = 4j + 1$, o primeiro jogador está em posição perdedora. - Se $n = 4j$, $4j + 2$ ou $4j + 3$, o primeiro jogador está em posição vencedora. 6. **Análise do passo:** O primeiro jogador pode remover 1, 2 ou 3 cartas, deixando o segundo jogador com $n-1$, $n-2$ ou $n-3$ cartas. - Se $n = 4j + 1$, então: - $n-1 = 4j$ (primeiro jogador vence) - $n-2 = 4j - 1$ (equivale a $4(j-1) + 3$, primeiro jogador vence) - $n-3 = 4j - 2$ (equivale a $4(j-1) + 2$, primeiro jogador vence) Assim, o segundo jogador sempre recebe uma posição vencedora, logo o primeiro jogador perde. - Se $n = 4j$, $4j + 2$ ou $4j + 3$, o primeiro jogador pode sempre escolher uma jogada que deixa o segundo jogador com $4j + 1$ cartas, posição perdedora para ele. 7. **Conclusão:** Por indução completa, mostramos que o primeiro jogador vence se $n = 4j$, $4j + 2$ ou $4j + 3$, e o segundo jogador vence se $n = 4j + 1$. **Resposta final:** O primeiro jogador vence para $n = 4j$, $4j + 2$ ou $4j + 3$ e o segundo jogador vence para $n = 4j + 1$, com $j$ inteiro não negativo.