Problema
Alberto e Barbara giocano al seguente gioco. Su un tavolo ci sono $ 1999 $ cerini, a turno possono toglierne un numero compreso fra 1 e la metà di quelli che rimangono sul tavolo. Perde chi lascia un solo cerino sul tavolo. Parte Barbara, dire chi ha una strategia vincente e descriverla.
Bonus question: Abbiamo $ N $ cerini e non $ 1999 $. Determinare tutti e soli gli $ N $ per cui Barbara ha una strategia vincente e tutti e soli gli $ N $ per cui la ha Alberto (questa parte è di mia "invenzione" quindi nn sono certo esista una soluzione buona se la mia non lo fosse)
I soliti A e B, il solito gioco
I soliti A e B, il solito gioco
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Claim: Alberto ha una strategia vincente se e solo se n appartiene alla seguente successione:
$ x_n=2^{n+1}+2^n-1 $
ovvero: 2,5,11,23,...,1535,3071... Quindi non per 1999 (valore per cui Barbara ha una strategia vincente). Per i restanti Barvara può sempre vincere.
Lemma 1: se ho $ x_n $ cerini non posso lasciare $ x_j $ cerini per qualsiasi n, j.
posso toglierne massimo $ 2^n+2^{n-1}-1 $ e minimo 1.
Devo lasciare quindi un numero di cerini compreso tra $ 2^n+2^{n+1}-2 $e $ 2^n+2^{n-1} $ entrambi maggiori di $ x_{n-1} $ .
Inoltre la sequenza $ x_i $ è cresciente quindi il lemma 1 è vero.
Lemma 2: se ho un numero m di cerini diverso da $ x_j $ posso sempre lasciarne $ x_i $.
m è sicuramente compreso tra due $ x_i $.
$ x_{n-1}+1\leq m \leq x_n-1 $
considero le due sequenze $ a_i $ (costituita da tutti i possibili numeri m in ordine cresciente):
$ 2^{n-1}+2^n; 2^{n-1}+2^n +1;...;2^{n+1}+2^n-2 $
e $ b_i $ (dei numeri compresi tra 1 e $ x_{n-1} $ in ordine cresciente ):
$ 1,2,....,2^{n-1}+2^n-1 $.
Verifico facilmente che a ciascun numero della prima sequenza posso togliere il corrispondente della seconda ottenendo $ x_{n-1} $.
La prima è cresciente, la seconda pure,inoltre in entrambe $ S_i+1=S_{i+1} $ , inoltre $ a_1>b_1 $ e ciò varrà per tutti.
Quindi il valore minimo di $ \frac{a_i}{b_i}= \frac{a_1+i-1}{b_1+i-1} $ si ha per $ i $ massimo.
Ovvero per:
$ \frac{2^{n+1}+2^n-2}{2^{n-1}+2^n-1}=2 $ quindi:
$ \frac{a_i}{b_i} \ge 2 $ e $ a_i \ge 2b_i $
Quindi per qualsiasi $ a_i $ posso togliere il corrispondente $ b_i $ e lasciare $ x_{n-1} $ cerini.
Lemma 3: ricevere $ x_i $ cerini è perdente.
Ipotizzo di avere $ x_i $ cerini.
Sarò obbligato a lasciare un numero di cerini m con $ x_i -1 \ge m \ge 1+x_{i-1} $
Per il lemma 2 il mio avversario mi può lasciare $ x_{i-1} $ cerini.
Proseguendo con questa strategia (di "disesa") il mio avversario mi può lasciare $ x_0 $ =2 cerini.
Con 2 cerini sono obbligato a lasciarne 1 e a perdere.
Analogamente se inizio con un numero di cerini differente da $ x_i $posso lasciarne $ x_i $ all'avversario che si troverebbe in posizione perdente.
Quindi Barbara vince per tutti gli n non appartenenti alla successione $ x_i $ e Alberto per i rimanenti.
$ x_n=2^{n+1}+2^n-1 $
ovvero: 2,5,11,23,...,1535,3071... Quindi non per 1999 (valore per cui Barbara ha una strategia vincente). Per i restanti Barvara può sempre vincere.
Lemma 1: se ho $ x_n $ cerini non posso lasciare $ x_j $ cerini per qualsiasi n, j.
posso toglierne massimo $ 2^n+2^{n-1}-1 $ e minimo 1.
Devo lasciare quindi un numero di cerini compreso tra $ 2^n+2^{n+1}-2 $e $ 2^n+2^{n-1} $ entrambi maggiori di $ x_{n-1} $ .
Inoltre la sequenza $ x_i $ è cresciente quindi il lemma 1 è vero.
Lemma 2: se ho un numero m di cerini diverso da $ x_j $ posso sempre lasciarne $ x_i $.
m è sicuramente compreso tra due $ x_i $.
$ x_{n-1}+1\leq m \leq x_n-1 $
considero le due sequenze $ a_i $ (costituita da tutti i possibili numeri m in ordine cresciente):
$ 2^{n-1}+2^n; 2^{n-1}+2^n +1;...;2^{n+1}+2^n-2 $
e $ b_i $ (dei numeri compresi tra 1 e $ x_{n-1} $ in ordine cresciente ):
$ 1,2,....,2^{n-1}+2^n-1 $.
Verifico facilmente che a ciascun numero della prima sequenza posso togliere il corrispondente della seconda ottenendo $ x_{n-1} $.
La prima è cresciente, la seconda pure,inoltre in entrambe $ S_i+1=S_{i+1} $ , inoltre $ a_1>b_1 $ e ciò varrà per tutti.
Quindi il valore minimo di $ \frac{a_i}{b_i}= \frac{a_1+i-1}{b_1+i-1} $ si ha per $ i $ massimo.
Ovvero per:
$ \frac{2^{n+1}+2^n-2}{2^{n-1}+2^n-1}=2 $ quindi:
$ \frac{a_i}{b_i} \ge 2 $ e $ a_i \ge 2b_i $
Quindi per qualsiasi $ a_i $ posso togliere il corrispondente $ b_i $ e lasciare $ x_{n-1} $ cerini.
Lemma 3: ricevere $ x_i $ cerini è perdente.
Ipotizzo di avere $ x_i $ cerini.
Sarò obbligato a lasciare un numero di cerini m con $ x_i -1 \ge m \ge 1+x_{i-1} $
Per il lemma 2 il mio avversario mi può lasciare $ x_{i-1} $ cerini.
Proseguendo con questa strategia (di "disesa") il mio avversario mi può lasciare $ x_0 $ =2 cerini.
Con 2 cerini sono obbligato a lasciarne 1 e a perdere.
Analogamente se inizio con un numero di cerini differente da $ x_i $posso lasciarne $ x_i $ all'avversario che si troverebbe in posizione perdente.
Quindi Barbara vince per tutti gli n non appartenenti alla successione $ x_i $ e Alberto per i rimanenti.
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
La soluzione di enomis è perfetta, niente da dire, tuttavia se l'avessi letta senza aver risolto il problema mi sarei incazzato, perchè è totalmente calata dall'alto. Visto che mi ha sempre dato fastidio leggere questo tipo di soluzione cercherò di spiegare, per i famosi utenti meno esperti (ma esistono davvero?) come si genera una soluzione simile, o almeno come si è generata nel mio microencefalo.
Allora
La prima cosa che faccio è guardare i casi piccoli
1--> perdo
2--> vinco
3--> può piazzarmela in 2 quindi perdo
4--> può piazzarmela in 2 quindi perdo
5--> non può più piazzarmela in 2, uh! vinco perchè poi io posso metterla in 2
Mumble mumble, quand'è il primo valore che lui non può piazzarmi in uno precedente vincente? Vediamo, lui può dimezzare, quindi il doppio è il massimo che funziona, quindi il doppio più 1 è il minimo che non funziona. Ogni volta quindi genero un vincente da quello precedente.
Quindi abbiamo la successione di numeri vincenti
$ a_0=2 $
$ a_{n+1}=2a_n+1 $
(a questo punto finisce il problema vero, mi calcolo a mano i termini, mi viene che 1535 è vincente, B riesce a giocarlo quindi vince, per la bonus question c'è la parte più "advanced")
Come calcoliamo l'ennesimo???
Visto che sappiamo calcolarle, ci piacerebbe tanto diventasse una progressione geometrica o aritmetica. Aritmetica è improbabile poichè il termine precedente va moltiplicato per qualcosa, proviamo geometrica. Dobbiamo compararla ad un altra successione che sia "linearmente uguale" (termine appena coniato, cioè che sia anch'essa in dipendenza solo dal valore precedente). Quindi prendiamo
$ b_n=a_n-k $
$ b_{n+1}+k=2b_n+2k+1 $
Ci piacerebbe tanto se $ k-2k-1=0 $ quindi $ k=-1 $
BELLO! Ora abbiamo la nostra successione $ b_n=a_n+1 $
Quindi
$ b_0=3 $
$ b_{n+1}=2b_n $
da cui $ b_n=3*2^n $
da cui $ a_n=3*2^n-1 $
Ma allora tutti questi sono vincenti!!!!
Sono anche i soli? Beh, certo, perchè se giochiamo un numero che non è di questi l'altro più giocare uno di questi poichè non esistono due numeri di quella successione A,B con A<B distanti l'uno più del doppio dall'altro (lo si vede moltiplicando)
Per la dimostrazione formale vedere due post sopra, non ho voglia di riscriverla e quella di enomis mi pare vada benissimo. Spero questa cosa vi sia piaciuta e serva a qualcuno
Allora
La prima cosa che faccio è guardare i casi piccoli
1--> perdo
2--> vinco
3--> può piazzarmela in 2 quindi perdo
4--> può piazzarmela in 2 quindi perdo
5--> non può più piazzarmela in 2, uh! vinco perchè poi io posso metterla in 2
Mumble mumble, quand'è il primo valore che lui non può piazzarmi in uno precedente vincente? Vediamo, lui può dimezzare, quindi il doppio è il massimo che funziona, quindi il doppio più 1 è il minimo che non funziona. Ogni volta quindi genero un vincente da quello precedente.
Quindi abbiamo la successione di numeri vincenti
$ a_0=2 $
$ a_{n+1}=2a_n+1 $
(a questo punto finisce il problema vero, mi calcolo a mano i termini, mi viene che 1535 è vincente, B riesce a giocarlo quindi vince, per la bonus question c'è la parte più "advanced")
Come calcoliamo l'ennesimo???
Visto che sappiamo calcolarle, ci piacerebbe tanto diventasse una progressione geometrica o aritmetica. Aritmetica è improbabile poichè il termine precedente va moltiplicato per qualcosa, proviamo geometrica. Dobbiamo compararla ad un altra successione che sia "linearmente uguale" (termine appena coniato, cioè che sia anch'essa in dipendenza solo dal valore precedente). Quindi prendiamo
$ b_n=a_n-k $
$ b_{n+1}+k=2b_n+2k+1 $
Ci piacerebbe tanto se $ k-2k-1=0 $ quindi $ k=-1 $
BELLO! Ora abbiamo la nostra successione $ b_n=a_n+1 $
Quindi
$ b_0=3 $
$ b_{n+1}=2b_n $
da cui $ b_n=3*2^n $
da cui $ a_n=3*2^n-1 $
Ma allora tutti questi sono vincenti!!!!
Sono anche i soli? Beh, certo, perchè se giochiamo un numero che non è di questi l'altro più giocare uno di questi poichè non esistono due numeri di quella successione A,B con A<B distanti l'uno più del doppio dall'altro (lo si vede moltiplicando)
Per la dimostrazione formale vedere due post sopra, non ho voglia di riscriverla e quella di enomis mi pare vada benissimo. Spero questa cosa vi sia piaciuta e serva a qualcuno
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
