Olimpiadi della Matematica Torino - OliMaTO - Forum

$(a)$ Si può vincere per $671$ valori di $n$, cioè per tutti e soli i multipli di $3$. Dimostriamo intanto che prima dell'ultima mossa, in caso di vittoria, ci sono $3$ graffette sul banco. Se l'ultima mossa toglieva $3$ graffette, allora prima di essa ce n'erano proprio $3$. Se l'ultima mossa toglieva metà delle graffette, allora prima di essa ce n'erano esattamente il doppio di $0$, cioè sempre $0$, ma questo è assurdo perché avrebbe già vinto in precedenza. Quindi prima dell'ultima mossa ci sono $3$ graffette. Ora notiamo che se $n$ è multiplo di $3$ significa che è della forma $3k$ con $k\in\mathbb{Z^+}$, quindi possiamo usare $k$ volte la mossa che toglie $3$ graffette e vincere. D'altra parte, se $n$ non è multiplo di $3$ ogni mossa porta ad avere di nuovo un numero di graffette che non è multiplo di $3$, infatti la mossa che ne toglie $3$ porta da $m$ graffette a $m-3$, e se $3$ dividesse $m-3$ dovrebbe dividere anche $n$, mentre se si usa la mossa che toglie metà delle graffette significa che prima erano pari, cioè della forma $2x$ con $x\in\mathbb{Z^+}$,quindi dopo la mossa saranno $x$, ma se $3$ dividesse $x$ dovrebbe dividere anche $2x$. Quindi visto che prima della mossa vincente ci devono essere $3$ graffette, cioè un multiplo di $3$, non si può vincere, e la tesi è dimostrata. Quindi si può vincere se e solo se $n$ è multiplo di $3$, cioè per $\lfloor\frac{2015}{3}\rfloor=671$ valori di $n$.
$(b)$ Si può vincere per $1344$ valori di $n$, cioè per tutti e soli quelli che non sono multipli di $3$. Infatti se $n$ non è multiplo di $3$ è della forma $3k+1$ o $3k+2$ con $k\in\mathbb{N}$, e usando $k$ volte la mossa che toglie $3$ graffette si arriva a $1$ o $2$ graffette. Nel primo caso abbiamo già vinto, nel secondo caso possiamo vincere con la mossa che toglie metà delle graffette. D'altra parte, se $n$ è multiplo di $3$ non si può vincere, perché ogni mossa ci porta ad avere un numero di graffette multiplo di $3$, mentre $1$ non lo è. Infatti se togliamo $3$ graffette passiamo da $x$ a $x-3$, e se $3\mid x$ deve essere anche $3\mid x-3$, e se ne togliamo metà passiamo da $2y$ a $y$, e se $3\mid2y$ deve essere anche $3\mid y$ in quanto $MCD(2,\ 3)=1$. Quindi la tesi è dimostrata, e si può vincere se e solo se $n$ non è multiplo di $3$, cioè per $2015-\lfloor\frac{2015}{3}\rfloor=2015-671=1344$ valori di $n$.