SNS 2014/15 n° 4

[Loara]

Clara e Guelfo giocano al seguente gioco: Partono con un numero e ognuno può decidere o di dividere il numero per un suo fattore primo o, se il numero è un quadrato perfetto, di estrarne la radice quadrata. esempio: se il numero di partenza è $16$, uno può decidere di dividere per $2$, e ottiene $8$, oppure di estrarre la radice, e ottiene $4$. A ognuno spetta una sola mossa, e vince chi, con l'ultima mossa ottiene $1$. Ognuno gioca con strategia ottimale ed inizia Clara.

• Dimostrare che se il numero di partenza è $3^{2014}$ vince Clara.
• Dimostrare che se il numero di partenza è $15^{4028}$ vince Guelfo.

Testo nascosto:

Il primo punto è semplice. Il secondo è più tosto di quanto possa sembrare (almeno per me )

[LucaMac]

• Basta che Clara continui a dividere per $3$ , lasciando così a Guelfo un numero della forma $3^{2n+1} $ che quindi non è un quadrato perfetto, obbligandolo allora a dividere per $3$ , fino a che Guelfo non restituisce $3^4$ a Clara, la quale estraendo la radice quadrata lascia $3^2$ , ora Guelfo è obbligato a lasciare $3$ e Clara può vincere ottenendo $1$.
• $15^{4028} = 3^{4028} \cdot 5^{4028} $
  Parlo di $(a,b)$ riferendomi al numero $3^a \cdot 5^b $.
  Guelfo può sempre lasciare Clara in modo tale che $ | a-b | = 2 $ , per dimostrarlo divido in due casi:
  1) se Clara alla prima mossa decide di dividere per un fattore primo, che sia WLOG $5$ , Guelfo può dividere ancora per $5$ , lasciando a Clara $(4028,4026)$ , infatti $ | 4028 - 4026 | = 2 $
  2) se Clara estrae la radice quadrata ottiene $(2014,2014)$ , quindi anche Guelfo la può estrarre, lasciando Clara con $(1007,1007)$ . Ora Clara deve dividere per un fattore primo, che sia WLOG $5$ , e Guelfo può quindi dividere ancora per $5$ lasciando a Clara $(1007,1005)$ , infatti $ | 1007 - 1005 | = 2 $
  Guelfo può fare in modo che $ |a-b| $ resti $2$ , per dimostrarlo divido in due casi:
  1) se Clara divide per un fattore primo, basta che Guelfo divida per l'altro , infatti $ | (a-1) - (b-1) | = |a-b| = 2 $
  2) se Clara estrae la radice quadrata lascia a Guelfo $ | \dfrac{a}{2} - \dfrac{b}{2} | = \dfrac{ |a-b| }{2} = 1 $ . Quindi Guelfo dividendo per l'opportuno fattore primo può sempre ottenere di rendere la differenza $2$ (Tranne se il minimo fra $a$ e $b$ è pari a $0$ , ma tale caso non interessa)
  Quindi, visto che ogni mossa fa diminuire almeno uno fra $a$ e $b$ , ad un certo punto si arriverà che Clara avrà , supponendo WLOG $a>b$ , $(3,1)$ oppure $(4,2)$ e Clara estrae la radice quadrata .
  Se è $(3,1)$ , Clara potrà quindi ora lasciare a Guelfo $(3,0)$ oppure $(2,1)$ , in entrambi i casi Guelfo può lasciare a Clara $(2,0)$ , obbligandola a lasciargli $(1,0)$ per poi vincere ottenendo $(0,0)$ . Infatti $3^0 \cdot 5^0 = 1 $.
  Se è $(4,2)$ , estraendo Clara la radice quadrata lascia a Guelfo $(2,1)$ che, analogamente, lo porta a vincere.

Spero di non aver commesso troppi errori...

[Loara]

Ottima soluzione, anche se volendo puntualizzare c'è un piccolo particolare che non và troppo bene:

2)[...] se Clara estrae la radice quadrata lascia a Guelfo $ | \dfrac{a}{2} - \dfrac{b}{2} | = \dfrac{ |a-b| }{2} = 1 $ . Quindi Guelfo dividendo per l'opportuno fattore primo può sempre ottenere di rendere la differenza $2$ (Tranne se il minimo fra $a$ e $b$ è pari a $0$ , ma tale caso non interessa)

Perché tale caso non interessa? Anzi, è molto interessante perché prima o poi tale caso compare. Secondo tale strategia, se il minimo tra $a$ e $b$ è $0$, allora l'altro numero deve essere per forza $2$ che è comunque perdente per Clara. Questo caso comunque lo hai spiegato dopo, ma secondo me sarebbe stato più corretto scrivere che avresti analizzato tale caso più tardi nella dimostrazione, ma non mi sembra giusto definirlo non interessante.

Bravo comunque per la dimostrazione del secondo punto .

[karlosson_sul_tetto]

Penso che intendesse il caso in cui (WLOG) $b'=\frac{b}{2}=0$ dopo la radice di Clara, la differenza tra $a$ e $b$ sarà di 1, e seguendo la strategia non potrebbe togliere un fattore primo a $b'$ perché è nullo, quindi non può rendere la differenza pari a 0. Almeno io l'ho interpretata cosi

[LucaMac]

Penso che intendesse il caso in cui (WLOG) $b'=\frac{b}{2}=0$ dopo la radice di Clara, la differenza tra $a$ e $b$ sarà di 1, e seguendo la strategia non potrebbe togliere un fattore primo a $b'$ perché è nullo, quindi non può rendere la differenza pari a 0. Almeno io l'ho interpretata cosi

Si, era questo che intendevo, ma effettivamente mi sono espresso abbastanza male..