SNS 2014/15 n° 4

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Loara
Messaggi: 40
Iscritto il: 07 set 2013, 17:25
Località: Salerno

SNS 2014/15 n° 4

Messaggio da 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 :P)
$ 210^2+211^2+212^2+213^2+214^2+215^2+216^2+217^2+218^2+219^2+220^2=\\ =221^2+222^2+223^2+224^2+225^2+226^2+227^2+228^2+229^2+230^2\\ 210=2*3*5*7 $
LucaMac
Messaggi: 180
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: SNS 2014/15 n° 4

Messaggio da 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... :D
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
Avatar utente
Loara
Messaggi: 40
Iscritto il: 07 set 2013, 17:25
Località: Salerno

Re: SNS 2014/15 n° 4

Messaggio da Loara »

Ottima soluzione, anche se volendo puntualizzare c'è un piccolo particolare che non và troppo bene:
LucaMac ha scritto: 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 :D.
$ 210^2+211^2+212^2+213^2+214^2+215^2+216^2+217^2+218^2+219^2+220^2=\\ =221^2+222^2+223^2+224^2+225^2+226^2+227^2+228^2+229^2+230^2\\ 210=2*3*5*7 $
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: SNS 2014/15 n° 4

Messaggio da 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 :)
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
LucaMac
Messaggi: 180
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: SNS 2014/15 n° 4

Messaggio da LucaMac »

karlosson_sul_tetto ha scritto: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.. :roll:
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
Rispondi