Italian TST 2005: problema n°6

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Simo_the_wolf
Moderatore
Messaggi: 1035
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Italian TST 2005: problema n°6

Messaggio da Simo_the_wolf » 22 mag 2005, 11:43

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?

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 23 mag 2005, 08:44

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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

oscar
Messaggi: 99
Iscritto il: 01 gen 1970, 01:00
Località: Ciriè Ciriè Eleyson

Messaggio da oscar » 23 mag 2005, 09:26

Si chiama Roberta, fidati ^.^
E a occhio direi anche che Alberto è mafioso..

Avatar utente
HarryPotter
Moderatore
Messaggi: 354
Iscritto il: 01 gen 1970, 01:00
Località: Pavia

Re: Italian TST 2005: problema n°6

Messaggio da HarryPotter » 23 mag 2005, 17:26

Simo_the_wolf ha scritto:Alberto e Roberta giocano a questo gioco
Lapsus froidiano...? :roll: :roll: :D

Simo_the_wolf
Moderatore
Messaggi: 1035
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 23 mag 2005, 20:37

E va bene, ho sbagliato, ma ammettete che Roberta è meglio di Barbara... :D

Comunque nessuno si è degnato di risolverlo... A parte marco la cui soluzione è ovviamente giusta... :D

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 23 mag 2005, 21:05

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!

MindFlyer

Messaggio da MindFlyer » 24 mag 2005, 05:15

Ok info, per il momento hai fatto quasi un punto.
Se dimostri il tuo guess per 2005 fai un punto.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 24 mag 2005, 14:33

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???

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 mag 2005, 15:23

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. []

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 24 mag 2005, 16:23

@ Mind: con calma... mica mi corre dietro nessuno :wink: ... 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 :lol:.... ci penserò bene e (se nessuno lo fà) posterò una sol completa scritta bene in seguito (ammettendo che arrivi in fondo)...

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 24 mag 2005, 16:32

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)]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 24 mag 2005, 16:42

Si pensavo di darmi allo studio delle lingue orientali il prox anno... come l'hai capito? :shock:

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

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 24 mag 2005, 18:18

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...
Ultima modifica di info il 24 mag 2005, 19:50, modificato 1 volta in totale.

MindFlyer

Messaggio da MindFlyer » 24 mag 2005, 18:22

Ok, ok, a quando qualche dimostrazione? :wink:

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 24 mag 2005, 18:52

Ho paura di avere sparato un'immensa cavolata e di avere fatto qualche errore... dopo cena controllo!

Ciao

Rispondi