Italian TST 2005: problema n°6
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Italian TST 2005: problema n°6
Alberto e Roberta giocano a questo gioco: fissato un numero $ N $ Alberto inizia e scrive $ 1 $ sulla lavagna. Successivamente, detto $ n $ il numero scritto sulla lavagna, una persona può decidere se scrivere $ n+1 $ o $ 2n $ con il limite che però non si può scrivere un numero maggiore di $ N $. Vince chi scrive sulla lavagna il numero $ N $.
(a) Determinate chi ha una strategia vincente per $ N=2005 $
(b) Determinate chi ha una strategia vincente per $ N=2004 $
(c) Quanti sono i numeri $ 1\leq N \leq 2005 $ tali che Barbara ha una strategia vincente?
(a) Determinate chi ha una strategia vincente per $ N=2005 $
(b) Determinate chi ha una strategia vincente per $ N=2004 $
(c) Quanti sono i numeri $ 1\leq N \leq 2005 $ tali che Barbara ha una strategia vincente?
- HarryPotter
- Moderatore
- Messaggi: 354
- Iscritto il: 01 gen 1970, 01:00
- Località: Pavia
Re: Italian TST 2005: problema n°6
Lapsus froidiano...?Simo_the_wolf ha scritto:Alberto e Roberta giocano a questo gioco
-
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Non dovrebbe essere troppo difficile, visto quello di geometria...
Credo basti contare e considerare quali sono i numeri vincenti e quelli perdenti con un procedimento a ritroso, per capire se l'1 è vincente o perdente... Per esempio se N=2005 (e suppongo per N dispari) i numeri pari sono vincenti, quelli dispari perdenti... gli altri casi (quelli con N pari) sono più complessi, dato che ad ogni potenza di 2 paiono invertirsi... ora però lascio stare... scrivevo solo per complimentarmi con il grande Simo... forza Abruzzo!
Credo basti contare e considerare quali sono i numeri vincenti e quelli perdenti con un procedimento a ritroso, per capire se l'1 è vincente o perdente... Per esempio se N=2005 (e suppongo per N dispari) i numeri pari sono vincenti, quelli dispari perdenti... gli altri casi (quelli con N pari) sono più complessi, dato che ad ogni potenza di 2 paiono invertirsi... ora però lascio stare... scrivevo solo per complimentarmi con il grande Simo... forza Abruzzo!
Certo che basta, ma va comunque detto!!
Io l'ho scritto così:
Nomenclatura: La mossa n-->n+1 la chiamo di incremento (mossa I) e n-->2n la chiamo di raddoppio (mossa R).
Caso dispari: Se N è dispari, allora A ha una strategia vincente.
Dim.: La strategia di A è giocare sempre mosse I. Così facendo si assicura la vittoria. Infatti: se A lascia un numero dispari, B è costretto a scrivere un numero pari (sia con un incremento che con un raddoppio). A gioca I, perciò risponde lasciando un numero dispari. Dato che la mossa di apertura è 1, che è dispari, con questa strategia B non è in grado di scrivere numeri dispari e quindi non può vincere.
Dato che però il gioco termina in un numero finito di mosse con la vittoria di uno dei due, vince senz'altro A. []
Io l'ho scritto così:
Nomenclatura: La mossa n-->n+1 la chiamo di incremento (mossa I) e n-->2n la chiamo di raddoppio (mossa R).
Caso dispari: Se N è dispari, allora A ha una strategia vincente.
Dim.: La strategia di A è giocare sempre mosse I. Così facendo si assicura la vittoria. Infatti: se A lascia un numero dispari, B è costretto a scrivere un numero pari (sia con un incremento che con un raddoppio). A gioca I, perciò risponde lasciando un numero dispari. Dato che la mossa di apertura è 1, che è dispari, con questa strategia B non è in grado di scrivere numeri dispari e quindi non può vincere.
Dato che però il gioco termina in un numero finito di mosse con la vittoria di uno dei due, vince senz'altro A. []
@ Mind: con calma... mica mi corre dietro nessuno ... o forse era un modo per dire che così non si risolve il punto c? (perchè il punto b si fà anche quello...).
Faccio il caso N dispari con il procedimento a ritroso; ora non ho tempo per fare altro: (v) stà per vincente; (p) stà per perdente;
N-1 (v) / N-2 (p) / N-3 (v) /... / (N-1)/2+1 (p) /
(N-1)/2 (v) / (N-1)/2-1 (p)/...
e così via.. continuando, analizzando un numero se chi gioca e si trova quel numero moltiplica per 2, darà al suo avversario sempre una posizione vincente. Se si trova un numero dispari e somma 1, darà al suo avversario un numero pari, ma tutti i pari scritti sono stati segnati con una (v) [e lo saranno anche quelli aggiunti], in questo modo tutti i numeri dispari sono perdenti. Se si trova un numero pari e somma 1, darà al suo avversario un numero dispari, ma tutti i dispari scritti sono stati segnati con una (p) [e lo saranno anche quelli aggiunti]: in questi modo tutti i numeri pari sono vincenti. Barbara ha un numero dispari: ha perso...
----- lo sò che è spiegato male
cmq per N pari pare escono prima un pò di (p) e (v) alternate, dopo una serie continua di (v), dopo ancora una serie di (v) e (p) alternate... N=2004 arriva in fondo e quindi Alberto è vincitore... devo ancora farlo bene però...
--------
E' da vedere se questo modo è il più veloce oppure se è meglio mostrare strategie effettive come hanno fatto Boll e Marco... mi pare si possa arrivare in fondo con entrambi i metodi... ora basta però che devo lavorare per la tesina .... ci penserò bene e (se nessuno lo fà) posterò una sol completa scritta bene in seguito (ammettendo che arrivi in fondo)...
Faccio il caso N dispari con il procedimento a ritroso; ora non ho tempo per fare altro: (v) stà per vincente; (p) stà per perdente;
N-1 (v) / N-2 (p) / N-3 (v) /... / (N-1)/2+1 (p) /
(N-1)/2 (v) / (N-1)/2-1 (p)/...
e così via.. continuando, analizzando un numero se chi gioca e si trova quel numero moltiplica per 2, darà al suo avversario sempre una posizione vincente. Se si trova un numero dispari e somma 1, darà al suo avversario un numero pari, ma tutti i pari scritti sono stati segnati con una (v) [e lo saranno anche quelli aggiunti], in questo modo tutti i numeri dispari sono perdenti. Se si trova un numero pari e somma 1, darà al suo avversario un numero dispari, ma tutti i dispari scritti sono stati segnati con una (p) [e lo saranno anche quelli aggiunti]: in questi modo tutti i numeri pari sono vincenti. Barbara ha un numero dispari: ha perso...
----- lo sò che è spiegato male
cmq per N pari pare escono prima un pò di (p) e (v) alternate, dopo una serie continua di (v), dopo ancora una serie di (v) e (p) alternate... N=2004 arriva in fondo e quindi Alberto è vincitore... devo ancora farlo bene però...
--------
E' da vedere se questo modo è il più veloce oppure se è meglio mostrare strategie effettive come hanno fatto Boll e Marco... mi pare si possa arrivare in fondo con entrambi i metodi... ora basta però che devo lavorare per la tesina .... ci penserò bene e (se nessuno lo fà) posterò una sol completa scritta bene in seguito (ammettendo che arrivi in fondo)...
Ma tu senti questo! Come ti permetti?? "Mi pare si possa arrivare in fondo"??? E' una dimostrazione completa e scritta come si deve, la mia!info ha scritto:E' da vedere se questo modo è il più veloce oppure se è meglio mostrare strategie effettive come hanno fatto Boll e Marco... mi pare si possa arrivare in fondo con entrambi i metodi...
Ok. Sto scherzando. La vera verità è che tutti e tre abbiamo scritto la stessa idea. Solo che due di tre l'hanno scritta in italiano. Rilancio con:
Bonus question: Dimostrare che tale strategia del caso dispari è sharp: se A sgarra anche solo una mossa, allora B può vincere. [facile, se avete risolto il punto (a)]
[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."
Si pensavo di darmi allo studio delle lingue orientali il prox anno... come l'hai capito?
Sul fatto che l'idea base è la stessa non c'è dubbio... il come viene attuata è diverso.
Io ho scelto quel procedimento perchè mi pare più facilmente generalizzabile ad N pari... (anche se ci devo ancora provare)... sicuramente il procedimento a ritroso permette di risolvere anche il punto (b)... Poi l'ho già detto io che è espresso male... vado di fretta...
E cmq per arrivare in fondo intendo "risolvere tutti e 3 i punti" ...
Ciao
Sul fatto che l'idea base è la stessa non c'è dubbio... il come viene attuata è diverso.
Io ho scelto quel procedimento perchè mi pare più facilmente generalizzabile ad N pari... (anche se ci devo ancora provare)... sicuramente il procedimento a ritroso permette di risolvere anche il punto (b)... Poi l'ho già detto io che è espresso male... vado di fretta...
E cmq per arrivare in fondo intendo "risolvere tutti e 3 i punti" ...
Ciao
Non ho ben controllato (anzi...), ma mi pare che il punto (c) venga così. Aspetto conferma o smentite:
I valori N buoni per la tipella si ottengono partendo dal numero K:=2 e applicando le trasformazioni
K:=K*4+2 o K:=K*4 (comodo il linguaggio TP4, no?), in un qualsiasi ordine, ma di modo che N risulti <=2005.
Poi il K finale ottenuto è N. Un grafo ad albero dice che i valori ammissibili sono 31...
I valori N buoni per la tipella si ottengono partendo dal numero K:=2 e applicando le trasformazioni
K:=K*4+2 o K:=K*4 (comodo il linguaggio TP4, no?), in un qualsiasi ordine, ma di modo che N risulti <=2005.
Poi il K finale ottenuto è N. Un grafo ad albero dice che i valori ammissibili sono 31...
Ultima modifica di info il 24 mag 2005, 19:50, modificato 1 volta in totale.