SNS mate 2014/2015

Scuola Normale Superiore, Sant'Anna, Indam, etc. Cosa studiare, come prepararsi.
PG93
Messaggi: 29
Iscritto il: 17 nov 2017, 16:52

Re: SNS mate 2014/2015

Messaggio da PG93 » 17 ago 2018, 13:28

Salve, il problema 4 mi da del filo da torcere :x, qualcuno potrebbe postare una soluzione per cortesia??

Parmenide
Messaggi: 9
Iscritto il: 30 mag 2018, 21:24

Re: SNS mate 2014/2015

Messaggio da Parmenide » 19 ago 2018, 23:09

Ci provo:

per la prima parte:
Testo nascosto:
interpretiamo le mosse in termini di esponenti. Possiamo dividere per 3, ovvero sottrarre 1 all'esponente, oppure estrarre la radice quadrata, ovvero dividere l'esponente per 2, se esso è pari.
Chiaramente il gioco finisce perché l'esponente diminuisce strettamente ad ogni turno.
La strategia utilizzata da Clara per vincere è la seguente: ad ogni suo turno lei sottrae uno all'esponente, così da lasciare Guelfo con esponente dispari, obbligandolo a sottrarre uno a sua volta. Quindi Clara si trova sempre un numero pari come esponente, giocando in questo modo; in particolare, detto $\alpha$ l'esponente che trova in un suo turno, con questa strategia al suo turno successivo trova $\alpha -2$. Continua in questo modo fino a quando non trova l'esponente 4; a quel punto estrae la radice, lasciando 2 a Guelfo; egli con una qualsiasi delle due mosse a disposizione deve lasciare a lei l'esponente 1, e quindi Clara vince
per la seconda parte:
Testo nascosto:
anche qui interpretiamo le mosse in termini di esponenti, chiamando $x$ l'esponente di 3 ad un certo punto del gioco e $y$ quello di 5:

Mossa 1: $(x;y)\rightarrow (x-1;y)$
Mossa 2: $(x;y)\rightarrow (x;y-1)$
Mossa 3: $(x;y)\rightarrow \left(\frac{x}{2};\frac{y}{2}\right)$ se $x,y$ sono pari

Distinguiamo due casi, a seconda della prima mossa di Clara.

Caso 1: Clara effettua $(4028;4028)\rightarrow (2014;2014)$
Guelfo risponde con $(2014;2014)\rightarrow (1007;1007)$
A questo punto Guelfo utilizza la strategia seguente: gioca la propria mossa affinché dopo il suo turno la differenza tra i due esponenti (in valore assoluto) sia 2. Dimostriamo che può sempre farlo per induzione:
Passo base: Clara effettua la mossa $(1007;1007)\rightarrow (1006;1007)$ (l'altra è simmetrica) e Guelfo risponde con $(1006;1007)\rightarrow (1005;1007)$
Passo induttivo: supponiamo $(x;y)$ tale che $x=y+2$ (l'altro caso è simmetrico) e Clara effettui la mossa 1 $(x;y)\rightarrow (x-1;y)$, allora Guelfo risponde con $(x-1;y)\rightarrow (x-1;y-1)$ (la stessa cosa vale per la mossa 2). Se $x,y$ sono entrambi pari, Clara può effettuare la mossa 3: $(x;y)\rightarrow \left(\frac{x}{2};\frac{y}{2}\right)$, tuttavia essendo $x=y+2$ si ha $\frac{x}{2}-\frac{y}{2}=1$ e quindi Guelfo può effettuare la mossa 2, ottenendo ciò che vuole.
In questo modo Guelfo riesce a lasciare a Clara la coppia $(0;2)$ (oppure la simmetrica). Clara giocando una mossa qualunque è costretta a lasciargli $(0;1)$ e quindi Guelfo vince.

Caso 2: Clara effettua la mossa $(4028;4028)\rightarrow (4027;4028)$ (l'altra è simmetrica)
Guelfo si comporta allo stesso modo mantenendo pari la differenza (in valore assoluto) tra i due esponenti, e vince come nel caso 1.
Correggetemi se qualcosa non va :D

PG93
Messaggi: 29
Iscritto il: 17 nov 2017, 16:52

Re: SNS mate 2014/2015

Messaggio da PG93 » 20 ago 2018, 13:29

A me pare giusto (ho trovato la stessa soluzione), grazie!
Unico problema, da stordito che sono ho scritto problema 4 mentre è il problema 3 che non riesco a fare... :roll:
Dunque mi farebbe comodo se qualcuno potesse postare la soluzione al 3 :D

Rispondi