Il gioco della divisibilità

Sì, Bob ha una strategia vincente; una di quelle possibili è partire scegliendo 2, 3, 4, 6, 16, 12. Consideriamo il resto modulo 12 del numero iniziale di Alice. Dopo il primo tentativo, se Bob non ha vinto, sappiamo che il numero iniziale è dispari, cioè può essere uguale a 1, 3, 4, 7, 9 oppure 11 mod 12. Se era uguale a 5 o 11 mod 12, tolto 2 rimane un multiplo di 3 mod 12, quindi Bob vince al secondo turno. Se era uguale a 1 o 9 mod 12, tolti 2 e 3 si ottiene 8 o 4 mod 12, quindi Bob vince al terzo turno. Se era uguale a 3 mod 12, tolti 2, 3 e 4 rimane uguale a 6 mod 12, q quindi Bob vince al quarto turno. L'unico caso che resta è il numero iniziale uguale a 7 mod 11; dopo aver tolto 2, 3, 4, 6 rimane uguale a 4 mod 12. Ora, togliendo 16 rimane 0 mod 12, e quindi 12 permette di terminare il gioco. La somma 2+3+4+6+16+12=43 è minore di 100, quindi Alice non può avere vinto.

Un'ultima parola

In questo caso la strategia greedy di partire con i numeri piccoli aiuta, ma poi bisogna temperarla...