I germogli ( semi o germogli , in inglese) è un gioco con due giocatori il tipo di pidocchio , inventato nel 1967 presso l' Università di Cambridge dai matematici John Horton Conway e Michael Paterson .
È indicato come il gioco della talpa peruviana alle pagine 58 e 59 nel 2 ° manuale per giovani castori .
Questo gioco è giocato per due giocatori con una penna e un foglio di carta. All'inizio ci sono n punti sul foglio. Ogni giocatore, a sua volta, collega un punto a un altro con una linea e aggiunge un nuovo punto su quella linea. Devono essere rispettati due vincoli: le linee non possono intersecarsi e un punto non può essere collegato a più di tre linee. Questo gioco è anche chiamato gioco di tiro, perché le figure raffigurate sembrano germogli di alberi.
Nella versione normale del gioco, il perdente è colui che non può più giocare senza violare entrambi i vincoli. C'è anche una versione di povertà , dove chi non può più giocare è il vincitore questa volta.
Il numero di punti tracciati sul foglio aumenta con ogni mossa, ed è quindi discutibile se il gioco finisce con un numero finito di mosse. Infatti, possiamo dimostrare che una partita finisce al massimo con 3n-1 mosse e almeno con 2n mosse.
La figura a fianco mostra un esempio di gioco, inizialmente con 2 punti. Il punto aggiunto da ogni giocatore è contrassegnato in rosso. Dopo 4 mosse, il gioco è finito, ed è il giocatore che ha giocato per primo che è quindi il perdente, poiché non può più giocare.
Per un dato numero di punti di partenza, uno dei due giocatori ha una strategia vincente. L'analisi del gioco consiste quindi in particolare nel determinare quale dei due giocatori ha una strategia vincente: o quello che gioca per primo, o quello che gioca per secondo. Questa analisi è stata eseguita manualmente fino a 6 punti di partenza.
Poi, nel 1990, David Applegate, Guy Jacobson e Daniel Sleator calcolarono quale giocatore avesse una strategia vincente fino a 11 punti di partenza. Questo risultato è stato poi esteso nel 2007 da Julien Lemoine e Simon Viennot fino a 32 punti di partenza, più cinque valori compresi tra 34 e 47 punti di partenza.
Nel caso della versione povertà, l'analisi del gioco è più difficile. Nel 1990, David Applegate, Guy Jacobson e Daniel Sleator hanno calcolato la strategia vincente fino a 9 punti di partenza. Questo risultato è stato esteso nel 2008 da Josh Purinton e Roman Khorkov fino a 16 punti di partenza.