Pagina 1 di 2
Italian TST 2005: problema n°6
Inviato: 22 mag 2005, 11:43
da Simo_the_wolf
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?
Inviato: 23 mag 2005, 08:44
da Marco
Allora, si chiama Roberta o Barbara?
Comunque, supponendo che Roberta e Barbara siano la stessa persona, ad occhio direi Alberto, Alberto e trentuno.
Ciao. M.
Inviato: 23 mag 2005, 09:26
da oscar
Si chiama Roberta, fidati ^.^
E a occhio direi anche che Alberto è mafioso..
Re: Italian TST 2005: problema n°6
Inviato: 23 mag 2005, 17:26
da HarryPotter
Simo_the_wolf ha scritto:Alberto e Roberta giocano a questo gioco
Lapsus froidiano...?
Inviato: 23 mag 2005, 20:37
da Simo_the_wolf
E va bene, ho sbagliato, ma ammettete che Roberta è meglio di Barbara...
Comunque nessuno si è degnato di risolverlo... A parte marco la cui soluzione è ovviamente giusta...
Inviato: 23 mag 2005, 21:05
da info
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!
Inviato: 24 mag 2005, 05:15
da MindFlyer
Ok info, per il momento hai fatto quasi un punto.
Se dimostri il tuo guess per 2005 fai un punto.
Inviato: 24 mag 2005, 14:33
da Boll
Scusate, sarò completamente accecato, ma per $ N=2005 $ non basta dire che la successione generata dal gioco è crescente e sicuramente finita , e che Alberto può sempre rimanere sui dispari rispondendo $ n+1 $ ad ogni mossa???
Inviato: 24 mag 2005, 15:23
da Marco
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. []
Inviato: 24 mag 2005, 16:23
da info
@ 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)...
Inviato: 24 mag 2005, 16:32
da Marco
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...
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!
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)]
Inviato: 24 mag 2005, 16:42
da info
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
Inviato: 24 mag 2005, 18:18
da info
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...
Inviato: 24 mag 2005, 18:22
da MindFlyer
Ok, ok, a quando qualche dimostrazione?
Inviato: 24 mag 2005, 18:52
da info
Ho paura di avere sparato un'immensa cavolata e di avere fatto qualche errore... dopo cena controllo!
Ciao