Si si... era un pò da modificare: l'ho fatto...
Mi scuso se ho riempito il forum di messaggi inutili e non ho invece controllato con esempi ciò che stavo facendo... Mi scuso inoltre per non poter scrivere ora la ragione di quanto detto sopra... lo farò in seguito...
Italian TST 2005: problema n°6
Tento di fare per bene almeno i punti a) e b), al c) sto ancora pensando
Conclusione Alberto vince sempre
Dimostrazione
Alberto=A
Barbara=B
Mossa che aggiunge 1: I
Mossa che raddoppia:R
Per $ N=2005 $, basta, come detto in precedenza, che A si matenga sempre sui dispari rispondendo sempre con la mossa I, e poichè il gioco è finito prima o poi andà avincere A perchè è l'unico che tocca dispari.
Per $ N=2004 $. A deve comunque rispondere sempre con la mossa I fino a che B non gli rende un pari compreso tra $ 502 $ e $ 1002 $, a quel punto risponderà con la mossa R, il gioco sarà quindi finito poichè, essendo il numero scritto maggiore di $ 1004 $ e mantenendosi A sempre sui pari rispondendo I, vincerà certamente. Proviamo dunque che effettivamente B non può fare a meno di toccare un pari fra $ 502 $ e $ 1002 $. Innanzitutto sicuramente B toccherà un numero di tale intervallo prima di A, poichè A risponde sempre con la mossa I, e il primo numero dell'intervallo è un pari. Ora, poniamo per assurdo che B non tocchi nessun numero di tale intervallo, B avrebbe dovuto saltare con una sola mossa più di $ 502 $ numeri partendo da un numero minore di $ 502 $. Il chè è evidentemente assurdo perchè B può solo raddoppiare o aggiungere, quindi la tesi è provata.
Conclusione Alberto vince sempre
Dimostrazione
Alberto=A
Barbara=B
Mossa che aggiunge 1: I
Mossa che raddoppia:R
Per $ N=2005 $, basta, come detto in precedenza, che A si matenga sempre sui dispari rispondendo sempre con la mossa I, e poichè il gioco è finito prima o poi andà avincere A perchè è l'unico che tocca dispari.
Per $ N=2004 $. A deve comunque rispondere sempre con la mossa I fino a che B non gli rende un pari compreso tra $ 502 $ e $ 1002 $, a quel punto risponderà con la mossa R, il gioco sarà quindi finito poichè, essendo il numero scritto maggiore di $ 1004 $ e mantenendosi A sempre sui pari rispondendo I, vincerà certamente. Proviamo dunque che effettivamente B non può fare a meno di toccare un pari fra $ 502 $ e $ 1002 $. Innanzitutto sicuramente B toccherà un numero di tale intervallo prima di A, poichè A risponde sempre con la mossa I, e il primo numero dell'intervallo è un pari. Ora, poniamo per assurdo che B non tocchi nessun numero di tale intervallo, B avrebbe dovuto saltare con una sola mossa più di $ 502 $ numeri partendo da un numero minore di $ 502 $. Il chè è evidentemente assurdo perchè B può solo raddoppiare o aggiungere, quindi la tesi è provata.
Bonjour… alura, dato che poi pensate che sono uno sparaballe, ecco qua… segnalate pure eventuali errori
Compiliamo per ogni N pari una colonna di questo tipo: a sinistra scriviamo i primi N numeri in ordine decrescente, a destra segniamo una v o una p a seconda che colui che si trova quel numero scritto sulla lavagna e deve giocare ha la possibilità (giocando bene) di vincere oppure no…
Partiamo dal caso N=2004, che ci servirà per studiare la situazione e generalizzare:
2004 p
2003 v
i primi due passi sono ovvi, d’ora in poi si segue questa logica. Se da un numero k si possono scrivere solo numeri con una v, la situazione è perdente, altrimenti è vincente (ricordo che si può solo aumentare il numero scritto). Divido il tutto in blocchi per comodità. Blocco1:
2002 p
2001 v
2000 p
…
1004 p
1003 v
ora abbiamo numeri abb piccoli da potere moltiplicare per 2. Dato che in questo modo si ottengono solo numeri pari (tutti segnati con una p), abbiamo una sfilza di v. Blocco2:
1002 v
…
502 v
ora, Blocco3:
501 p
500 v
499 p
…
2 v
1p
e quindi il secondo giocatore perde….
Cosa possiamo osservare per generalizzare? Se N è pari, il primo blocco è del tipo (P,D)=(p,v) [chiarisco P stà per pari e D per dispari: associando con questa scrittura voglio dire che i pari sono perdenti ed e dispari vincenti, (P,D)=(v,p) avrebbe significato opposto]. Il secondo blocco comincia con N/2 ed è sempre una serie di (P,D)=(v,v), il terzo blocco comincia con [N/4] se [N/2] è pari oppure con [N/2-1]/2 se (N/2) è dispari. In ogni caso uscirà fuori un blocco (P,D)=(p,v) oppure (P,D)=(v,p) a seconda che il terzo blocco cominci con un numero pari o un numero dispari, dato che il primo numero del blocco è sempre perdente.
Come ulteriori osservazioni, diciamo che se si ottiene un blocco (P,D)=(v,p) questo è l’ultimo blocco che si compilerà. Infatti, dopo avere compilato questo blocco, andando avanti la mossa che moltiplica il numero per 2 darà sempre un numero pari vincente (per l’avversario) e quindi l’unica soluzione sarà sommare sempre 1, e la compilazione segue.
Invece, se si ottiene un blocco (P,D)=(p,v), proseguendo ci si ritroverà sempre con un blocco caratterizzato da (P,D)=(v,v)… infatti se si moltiplica per 2 si darà sempre all’avversario un numero perdente.
Noi vogliamo fare vincere Barbara e quindi non ci deve mai essere un blocco (P,D)=(v,p) che porterebbe ad un 1 perdente.
Per fare questo vediamo la sequenza dei blocchi, come si succede. Ecco un algoritmo. Il blocco 2 inizia con N/2, come detto sopra:
N/2 è pari il blocco successivo inizia con N_3=N/2
N/2 è dispari il blocco successivo inizia con N_3=(N-1)/2
N_3 DEVE essere pari per far vincere Barbara.
N_4=N_3/2
N_4/2 è pari il blocco successivo inizia con N_5=N_2/2
N_4/2 è dispari il blocco successivo inizia con N_5=(N_4-1)/2
N_5 DEVE essere pari come prima…i
N_6=N_5/2
… e così via!
Per chiarezza N_4 ed N_6 sono i numeri iniziali di blocchi del tipo (P,D)=(v,v)… Alla fine non si arriva con un blocco (P,D)=(v,v) [anche senza verificarlo, ce la caviamo dicendo che si avrebbe che si Angelo che Barbare giocando al meglio potrebbero vincere, ma la prima mossa di Angelo sarebbe obbligata a dare la vittoria a barbara: assurdo!]… Per far vincere Barbare quindi basta porre la condizione che non si presenti mai (P,D)=(v,p)…
La fine del procedimento sopra giunge con un N_k=1 (cioè con blocco k che inizia e finisce con 1). Questo perché si continua a dividere per 2: se una serie inizia con un numero >1, finisce sempre con un numero >1, come è facile verificare. Questo ci aiuta per svolgere il procedimento al contrario.
Partendo da 1, si moltiplica per 2 (notiamo infatti che l'ultima mossa è stato un "diviso 2"; se fosse stato un "meno uno diviso due" l'uno sarebbe un numero perdente seguente un blocco (P,D)=(v,v); poi facendo il procedimento inverso, o si moltiplica per 2, oppure si moltiplica per 2 e si aggiunge 1. Poi però si moltiplica per 2. poi o si moltiplica per 2 oppure si moltiplica per 2 e si aggiunge 1; si moltiplica per 2. Poi un’altra scelta. Poi ancora per 2… e così via. Ci possiamo fermare dopo una qualsiasi moltiplicazione per 2 ed ottenere un N che permetta a Barbara di vincere.
Dato che K:=2*K+1 seguito da un *2 risulta K:=K*4+2, otteniamo la formula che ho scritto in precedenza. Un grafo ad albero indica che i valori ammissibili sono 31, tra questi 2,8,10,16,32,40…
In effetti è estremamente lunga da scrivere… fatemi sapere se ci sono errori…ho cercato di essere chiaro ma non so se ci sono riuscito…
Compiliamo per ogni N pari una colonna di questo tipo: a sinistra scriviamo i primi N numeri in ordine decrescente, a destra segniamo una v o una p a seconda che colui che si trova quel numero scritto sulla lavagna e deve giocare ha la possibilità (giocando bene) di vincere oppure no…
Partiamo dal caso N=2004, che ci servirà per studiare la situazione e generalizzare:
2004 p
2003 v
i primi due passi sono ovvi, d’ora in poi si segue questa logica. Se da un numero k si possono scrivere solo numeri con una v, la situazione è perdente, altrimenti è vincente (ricordo che si può solo aumentare il numero scritto). Divido il tutto in blocchi per comodità. Blocco1:
2002 p
2001 v
2000 p
…
1004 p
1003 v
ora abbiamo numeri abb piccoli da potere moltiplicare per 2. Dato che in questo modo si ottengono solo numeri pari (tutti segnati con una p), abbiamo una sfilza di v. Blocco2:
1002 v
…
502 v
ora, Blocco3:
501 p
500 v
499 p
…
2 v
1p
e quindi il secondo giocatore perde….
Cosa possiamo osservare per generalizzare? Se N è pari, il primo blocco è del tipo (P,D)=(p,v) [chiarisco P stà per pari e D per dispari: associando con questa scrittura voglio dire che i pari sono perdenti ed e dispari vincenti, (P,D)=(v,p) avrebbe significato opposto]. Il secondo blocco comincia con N/2 ed è sempre una serie di (P,D)=(v,v), il terzo blocco comincia con [N/4] se [N/2] è pari oppure con [N/2-1]/2 se (N/2) è dispari. In ogni caso uscirà fuori un blocco (P,D)=(p,v) oppure (P,D)=(v,p) a seconda che il terzo blocco cominci con un numero pari o un numero dispari, dato che il primo numero del blocco è sempre perdente.
Come ulteriori osservazioni, diciamo che se si ottiene un blocco (P,D)=(v,p) questo è l’ultimo blocco che si compilerà. Infatti, dopo avere compilato questo blocco, andando avanti la mossa che moltiplica il numero per 2 darà sempre un numero pari vincente (per l’avversario) e quindi l’unica soluzione sarà sommare sempre 1, e la compilazione segue.
Invece, se si ottiene un blocco (P,D)=(p,v), proseguendo ci si ritroverà sempre con un blocco caratterizzato da (P,D)=(v,v)… infatti se si moltiplica per 2 si darà sempre all’avversario un numero perdente.
Noi vogliamo fare vincere Barbara e quindi non ci deve mai essere un blocco (P,D)=(v,p) che porterebbe ad un 1 perdente.
Per fare questo vediamo la sequenza dei blocchi, come si succede. Ecco un algoritmo. Il blocco 2 inizia con N/2, come detto sopra:
N/2 è pari il blocco successivo inizia con N_3=N/2
N/2 è dispari il blocco successivo inizia con N_3=(N-1)/2
N_3 DEVE essere pari per far vincere Barbara.
N_4=N_3/2
N_4/2 è pari il blocco successivo inizia con N_5=N_2/2
N_4/2 è dispari il blocco successivo inizia con N_5=(N_4-1)/2
N_5 DEVE essere pari come prima…i
N_6=N_5/2
… e così via!
Per chiarezza N_4 ed N_6 sono i numeri iniziali di blocchi del tipo (P,D)=(v,v)… Alla fine non si arriva con un blocco (P,D)=(v,v) [anche senza verificarlo, ce la caviamo dicendo che si avrebbe che si Angelo che Barbare giocando al meglio potrebbero vincere, ma la prima mossa di Angelo sarebbe obbligata a dare la vittoria a barbara: assurdo!]… Per far vincere Barbare quindi basta porre la condizione che non si presenti mai (P,D)=(v,p)…
La fine del procedimento sopra giunge con un N_k=1 (cioè con blocco k che inizia e finisce con 1). Questo perché si continua a dividere per 2: se una serie inizia con un numero >1, finisce sempre con un numero >1, come è facile verificare. Questo ci aiuta per svolgere il procedimento al contrario.
Partendo da 1, si moltiplica per 2 (notiamo infatti che l'ultima mossa è stato un "diviso 2"; se fosse stato un "meno uno diviso due" l'uno sarebbe un numero perdente seguente un blocco (P,D)=(v,v); poi facendo il procedimento inverso, o si moltiplica per 2, oppure si moltiplica per 2 e si aggiunge 1. Poi però si moltiplica per 2. poi o si moltiplica per 2 oppure si moltiplica per 2 e si aggiunge 1; si moltiplica per 2. Poi un’altra scelta. Poi ancora per 2… e così via. Ci possiamo fermare dopo una qualsiasi moltiplicazione per 2 ed ottenere un N che permetta a Barbara di vincere.
Dato che K:=2*K+1 seguito da un *2 risulta K:=K*4+2, otteniamo la formula che ho scritto in precedenza. Un grafo ad albero indica che i valori ammissibili sono 31, tra questi 2,8,10,16,32,40…
In effetti è estremamente lunga da scrivere… fatemi sapere se ci sono errori…ho cercato di essere chiaro ma non so se ci sono riuscito…
Ok. La sol di Info sembra reggere, ma è scritta in esperanto. Caro Info, quando devi fare le dimostrazioni "...e così via...", con un pochino più di sforzo, puoi anche metterla in bella calligrafia con l'induzione. Ecco la mia.
------------------------------
Caso pari: Se N è pari e maggiore di due, allora ha una strategia vincente lo stesso giocatore che ce l'ha nel caso N' = [N/4].
Le [ ] indicano la parte intera, come al solito.
Dim.: Sia G il gioco originario, e G' il gioco con obiettivo N', di cui ammettiamo di conoscere la strategia vincente. Sia X il giocatore che ha una s.v. per G'.
La strategia di X è:
- giocare secondo la strategia di G', se l'ultimo numero scritto è < N';
- se invece l'ultimo numero scritto è >= N', raddoppiare se può. Altrimenti incrementare.
Con questa strategia X vince. Infatti: dimostrerò per induzione che l'avversario di X (che chiamo Y) scrive sempre:
(a) - numeri minori di N' e perdenti per G', oppure
(b) - numeri maggiori di N' e minori o uguali a 2N', oppure
(c) - numeri dispari maggiori di 2N'.
Viceversa, proverò che X è sempre in grado di scrivere:
(d) - numeri minori di N' e vincenti per G', oppure
(e) - N', oppure
(f) - numeri pari maggiori di 2N'.
(si noti che (a)-(f) sono una partizione dei numeri <= N)
Se 1 è vincente per G', allora X è A e vale (d), se invece è perdente per G', allora X è B e vale (a).
Se sono stati giocati solo numeri < N' (casi (a) o (d) ), allora sappiamo che X gioca numeri vincenti per G' e Y perdenti per come abbiamo scelto X e Y, quindi vale (a) o (d) o (e).
Y non può mai giocare N' (dato che X sta giocando in modo da impedirglielo).
Se X ha giocato un numero < N' e Y decide di superare N', allora significa che sceglie una mossa R e perciò scrive un numero <2N', quindi vale (b).
Se X ha giocato N', allora qualunque risposta scelga Y, scrive numeri >N' e <=2N' e si ricade sotto (b).
Se l'ultima risposta di Y è di tipo (b), X raddoppia. Lo può fare, dato che 4N'<=N. In tal caso, X scrive un numero pari >2N', cioè vale (f).
Se l'ultimo numero scritto è >2N' (e quindi siamo nei casi (c) o (f) ), allora non si può più raddoppiare (perché si sballerebbe sopra N). Quindi entrambi possono giocare solo mosse I e, se è Y a giocare, gioca numeri dispari, quindi vale (c), mentre se è X, gioca numeri pari, quindi (f).
Siccome N ricade sotto il caso (f), Y non è in grado di vincere e la strategia descritta è vincente per X. []
Caso 2: N=2 è vincente per B.
Dim.: Ovvio. []
(il caso 2 richiede un trattamento a parte, perché il criterio del caso pari generico non funzionerebbe, dato che N'=0)
Soluzione
Quanto sopra dimostrato permette di affermare che i casi vincenti per B sono:
- 2
- 4N, se N è vincente per B
- 4N+2, se N è vincente per B.
Tutti gli altri N sono vincenti per A. Da questo segue che le risposte ai tre quesiti sono Alberto, Alberto e trentuno.
Per contare il 31, invece che disegnare strani alberi, si può osservare che la generazione per ricorrenza trovata ha una struttura in qualche senso frattale, con blocchi di $ 2^k $ valori vincenti per B, che partono da $ 2^{2k-1} $.
L'ultimo blocco è quello che comincia con $ 512=2^9; (k=4) $, quindi il numero è la somma delle potenze di due da 1 a 16 (ossia 31).
Ciao. M.
------------------------------
Caso pari: Se N è pari e maggiore di due, allora ha una strategia vincente lo stesso giocatore che ce l'ha nel caso N' = [N/4].
Le [ ] indicano la parte intera, come al solito.
Dim.: Sia G il gioco originario, e G' il gioco con obiettivo N', di cui ammettiamo di conoscere la strategia vincente. Sia X il giocatore che ha una s.v. per G'.
La strategia di X è:
- giocare secondo la strategia di G', se l'ultimo numero scritto è < N';
- se invece l'ultimo numero scritto è >= N', raddoppiare se può. Altrimenti incrementare.
Con questa strategia X vince. Infatti: dimostrerò per induzione che l'avversario di X (che chiamo Y) scrive sempre:
(a) - numeri minori di N' e perdenti per G', oppure
(b) - numeri maggiori di N' e minori o uguali a 2N', oppure
(c) - numeri dispari maggiori di 2N'.
Viceversa, proverò che X è sempre in grado di scrivere:
(d) - numeri minori di N' e vincenti per G', oppure
(e) - N', oppure
(f) - numeri pari maggiori di 2N'.
(si noti che (a)-(f) sono una partizione dei numeri <= N)
Se 1 è vincente per G', allora X è A e vale (d), se invece è perdente per G', allora X è B e vale (a).
Se sono stati giocati solo numeri < N' (casi (a) o (d) ), allora sappiamo che X gioca numeri vincenti per G' e Y perdenti per come abbiamo scelto X e Y, quindi vale (a) o (d) o (e).
Y non può mai giocare N' (dato che X sta giocando in modo da impedirglielo).
Se X ha giocato un numero < N' e Y decide di superare N', allora significa che sceglie una mossa R e perciò scrive un numero <2N', quindi vale (b).
Se X ha giocato N', allora qualunque risposta scelga Y, scrive numeri >N' e <=2N' e si ricade sotto (b).
Se l'ultima risposta di Y è di tipo (b), X raddoppia. Lo può fare, dato che 4N'<=N. In tal caso, X scrive un numero pari >2N', cioè vale (f).
Se l'ultimo numero scritto è >2N' (e quindi siamo nei casi (c) o (f) ), allora non si può più raddoppiare (perché si sballerebbe sopra N). Quindi entrambi possono giocare solo mosse I e, se è Y a giocare, gioca numeri dispari, quindi vale (c), mentre se è X, gioca numeri pari, quindi (f).
Siccome N ricade sotto il caso (f), Y non è in grado di vincere e la strategia descritta è vincente per X. []
Caso 2: N=2 è vincente per B.
Dim.: Ovvio. []
(il caso 2 richiede un trattamento a parte, perché il criterio del caso pari generico non funzionerebbe, dato che N'=0)
Soluzione
Quanto sopra dimostrato permette di affermare che i casi vincenti per B sono:
- 2
- 4N, se N è vincente per B
- 4N+2, se N è vincente per B.
Tutti gli altri N sono vincenti per A. Da questo segue che le risposte ai tre quesiti sono Alberto, Alberto e trentuno.
Per contare il 31, invece che disegnare strani alberi, si può osservare che la generazione per ricorrenza trovata ha una struttura in qualche senso frattale, con blocchi di $ 2^k $ valori vincenti per B, che partono da $ 2^{2k-1} $.
L'ultimo blocco è quello che comincia con $ 512=2^9; (k=4) $, quindi il numero è la somma delle potenze di due da 1 a 16 (ossia 31).
Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
