O Sprouts ( sementes , ou brotos , em inglês) é um jogo com dois jogadores do tipo piolho , inventado em 1967 na Universidade de Cambridge pelos matemáticos John Horton Conway e Michael Paterson .
É referido como a Mole Jogo peruana nas páginas 58 e 59 do 2 nd Handbook for júnior Beavers .
Este jogo é jogado por dois jogadores com uma caneta e uma folha de papel. No início, existem n pontos na folha. Cada jogador, por sua vez, conecta um ponto a outro com uma linha e adiciona um novo ponto a essa linha. Duas restrições devem ser respeitadas: as linhas não podem se cruzar e um ponto não pode ser conectado a mais de três linhas. Este jogo também é chamado de jogo de tiro, porque as figuras representadas parecem brotos de árvore.
Na versão normal do jogo, o perdedor é aquele que não pode mais jogar sem violar ambas as restrições. Há também uma versão de pobreza , onde quem não pode mais jogar é o vencedor desta vez.
O número de pontos plotados na folha aumenta com cada jogada, e, portanto, é questionável se o jogo termina em um número finito de jogadas. Na verdade, podemos mostrar que um jogo termina no máximo com 3n-1 movimentos e pelo menos com 2n movimentos.
A figura ao lado dá um exemplo de jogo, inicialmente com 2 pontos. O ponto adicionado por cada jogador é marcado em vermelho. Após 4 jogadas, o jogo termina e é o jogador que jogou primeiro que é portanto o perdedor, uma vez que já não pode jogar.
Para um determinado número de pontos de partida, um dos dois jogadores tem uma estratégia vencedora. A análise do jogo consiste, portanto, em particular em determinar qual dos dois jogadores tem uma estratégia vencedora: ou quem joga primeiro, ou quem joga segundo. Esta análise foi realizada manualmente até 6 pontos de partida.
Então, em 1990, David Applegate, Guy Jacobson e Daniel Sleator computador calcularam qual jogador tem uma estratégia vencedora de até 11 pontos de partida. Este resultado foi então estendido em 2007 por Julien Lemoine e Simon Viennot até 32 pontos de partida, mais cinco valores entre 34 e 47 pontos de partida.
No caso da versão de pobreza, a análise do jogo é mais difícil. Em 1990, David Applegate, Guy Jacobson e Daniel Sleator calcularam a estratégia de vitória até 9 pontos de partida. Este resultado foi estendido em 2008 por Josh Purinton e Roman Khorkov até 16 pontos de partida.