A Cesenatico si fanno tanti giochi

Esercizi sulla verità delle proposizioni e problemi che non sembrano rientrare in nessun'altra categoria.

A Cesenatico si fanno tanti giochi

Messaggioda cip999 » 02/05/2015, 14:23

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?
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 582
Iscritto il: 26/02/2014, 16:47

Re: A Cesenatico si fanno tanti giochi

Messaggioda Federico II » 02/05/2015, 18:44

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 è?
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 428
Iscritto il: 14/05/2014, 14:53

Re: A Cesenatico si fanno tanti giochi

Messaggioda cip999 » 02/05/2015, 19:13

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... :D

Questo è un 2000/4.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 582
Iscritto il: 26/02/2014, 16:47

Re: A Cesenatico si fanno tanti giochi

Messaggioda Giovanni98 » 21/06/2015, 15:49

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 :)
Avatar utente
Giovanni98
 
Messaggi: 1242
Iscritto il: 27/11/2014, 14:30


Torna a Logica e Matematizzazione

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite