A Cesenatico si fanno tanti giochi

[cip999]

Fissato un intero $n > 1$, Alberto e Barbara fanno il seguente gioco:

1. Alberto sceglie un intero positivo;
2. Barbara sceglie un intero maggiore di $1$ che sia multiplo o sottomultiplo del numero di Alberto (compreso il numero stesso);
3. Alberto restituisce a Barbara il numero da lei detto, eventualmente aggiungendo o togliendo $1$;

il gioco prosegue ripetendo alternativamente i passi 2 e 3. Barbara vince se riesce a scegliere $n$ entro $50$ mosse. Per quali valori di $n$ Barbara può vincere contro qualunque strategia di Alberto?

[Federico II]

Soluzione

Testo nascosto:

Barbara ha una strategia vincente se e solo se $n$ è multiplo di $6$.
Se $n$ è multiplo di $6$, descriviamo una strategia per Barbara. Se il primo numero scelto da Alberto è pari, Barbara sceglie $2$ e poi Alberto può scegliere $1$, $2$ o $3$: in ogni caso a questo punto Barbara può scegliere qualsiasi multiplo di $6$. Se il primo numero scelto da Alberto è dispari, Barbara sceglie il triplo di tale numero. A questo punto Alberto può scegliere solo un numero pari (se cambia il numero di Barbara, che è dispari) o un multiplo di $3$ (se lo lascia invariato). Nel primo caso Barbara sceglie $2$ e vince al suo turno successivo come descritto sopra. Nel secondo caso Barbara sceglie $3$ e poi Alberto può scegliere $2$, $3$ o $4$: nei primi due casi Barbara può vincere subito, nel terzo sceglie $2$ e vince al suo turno successivo. In ogni caso quindi Barbara vince dopo meno di $50$ mosse. Se $n$ non è multiplo di $6$, dimostriamo che Alberto ha una strategia vincente. Tale strategia consiste nel non scegliere mai multipli o divisori di $n$, perché è solo se lui sceglie uno di questi numeri che subito dopo Barbara può vincere. Se infatti Alberto non ne sceglie mai, passeranno sicuramente più di $50$ mosse prima che Barbara riesca a vincere (Alberto può prolungare il gioco all'infinito). Alla prima mossa può scegliere un numero qualsiasi, quindi può attuare la sua strategia (ricordiamo che $n>1$ quindi non tutti i numeri sono suoi multipli o divisori). Successivamente indichiamo con $k$ il numero che riceve da Barbara. Alberto può scegliere $k-1$, $k$ o $k+1$. Se $k>n+1$, tra di essi non ci sono divisori di $n$ in quanto questi sono minori o uguali a $n$. Dal momento che $n\geq2$ almeno uno tra i tre non sarà multiplo di $n$ (almeno due se $n\geq3$), quindi Alberto può scegliere tale numero. Se $k=n$ oppure $k=n+1$, Alberto sceglie $n+1$, che è coprimo con $n$ in quanto sono due numeri consecutivi, quindi non può essere né un suo multiplo né un suo divisore (si dovrebbe avere $n=1$, assurdo). Se $k=n-1$, Alberto lascia $k$ invariato. Tale $k$ è coprimo con $n$ in quanto sono due numeri consecutivi, e non può essere quindi suo multiplo o divisore, tranne nel caso $k=1$, che è però da escludere perché Barbara non può scegliere $1$. Se $k<n-1$, nessuno dei tre numeri che può scegliere Alberto è un multiplo di $n$ in quanto questi sono maggiori o uguali a $n$. Se almeno uno non è divisore di $n$ Alberto sceglie quello. Se sono tutti e tre divisori di $n$ tra di essi ce n'è almeno uno divisibile per $3$ e almeno uno pari, quindi $n$ è divisibile per $2$ e per $3$, quindi per $6$, in contraddizione con quanto avevamo supposto. Quindi la tesi è dimostrata.

PS: Di che anno è?

[cip999]

Ok, l'ho fatto praticamente identico... Alla fine potevi risparmiarti il caso $k = n$ che non può esistere e fare direttamente $k \ge n + 1$ e $k \le n - 1$, ma sono pignolerie...

Questo è un 2000/4.

[Giovanni98]

Non si potrebbe anche risolvere così?

Barbara vince sse l'intero $t $ che é capitato ad Alberto è tale che $t (t-1)(t+1) | n $ oppure che $n | t $ e $n|t - 1$ e $n | t+1$. Il secondo caso é impossibile poiché $n > 1$ mentre il primo é possibile sse $6 | n $ ed infatti in tal caso esiste una strategia per Barbara che é quella descritta da Federico.

Fatemi sapere