Newsgroup: it.hobby.enigmi
Titolo: (MA) Un semplice gioco...

Due giocatori si alternano nello scegliere un numero e sommarlo al totale
raggiunto. Il numero scelto deve essere minore della metà del totale, che
inizialmente parte da 2. Lo scopo è arrivare a 1000 (generalizzando: a un
valore N). Chi vince fra i due, e qual è la strategia?
Ciao
Andrea

"Andrea Artesiani" <overma...@LEVAMIlibero.it> wrote in message
news:01c20bac$2fda20a0$LocalHost@default...

Per minore intendi strettamente minore? Se così fosse, da 2 non ci si esce,
visto che non possiamo aggiungere neanche una unità (1 non è minore della
metà di 2). Quindi assumo che tu intenda "minore o uguale"
Un totale parziale è perdente se, trovandecelo davanti ed avendo noi la
mano, non possiamo fare niente per evitare la sconfitta.
Evidentemente 1000 è perdente.
Sono vincenti quei parziali che ci permettono di fare una giocata che lascia
l'avversario con un parziale perdente.
Quindi tutti i numeri x da 999 a 667 sono vincenti, perché distano da 1000
per meno della loro metà, ovvero (1000-x)<(x/2) ovvero x>2/3*1000, che è
vero a partire dal valore x=[2/3*1000]=667 ([] è la parte intera superiore).
666 è invece perdente, perché da lì non si riesce ad arrivare a 1000 e
d'altra parte almeno 1 lo si deve aggiungere, lasciando l'avversario in
posizione vincente. Proseguendo il prossimo perdente è x=[2/3*666]-1=443,
che è il più piccolo parziale dal quale non si può raggiungere 666. Poi
vengono 295, 195, 130, 86, 57, 37, 24, 15, 9, 5, 3, 1.
2 non è nell'elenco, quindi è vincente!
Chi comincia vince, dato che alla prima mossa lascia l'avversario con 3 che
perde.
Ad esempio, se si dovesse raggiungere 26, il 2 sarebbe perdente. Gli altri
perdenti sarebbero 26,17,11,7,4,2 per cui al secondo di mano (che si troverà
subito di fronte ad un 3) basterà raggiungere sempre quei parziali per
vincere.
In generale, si parte da N e si cominncia a moltiplicare per 2/3,
arrotondando per eccesso e poi togliendo 1. Se la catena passa per il 2
allora chi inizia perde, altrimenti vince.
Ciao, Silv:o)

 Per minore intendi strettamente minore? Se così fosse, da 2 non ci si
esce,
Scusa, ho mescolato due diversi giochi: qui bisogna sommare numeri
strettamente minori del totale, la metà non c'entra :-(
Il tuo ragionamento però è quello giusto e il risultato si semplifica un
po'!
Ciao
Andrea

 2 non č nell'elenco, quindi č vincente!
Correggo (anche se non cambia nulla delle conclusioni): 196 (non 195)
Inoltre, 1 č un parziale di partenza ovviamente impossibile.
Qualora, come detto da Andrea, il numero scelto debba essere "minore"
della meta' del totale (e non "minore o uguale"), ovviamente, dal 2
non ci si esce. Supponiamo pero' di partire da 3.
Anche in questo caso (per arrivare a 1000) chi comincia vince,
potendo raggiungere 4, 6, 10, 16, 25, 38, 58, 87, 131, 197, 296, 444,
666 e 1000 (dal target basta moltiplicare di volta in volta per 2/3,
eliminando gli eventuali decimali).
Ciao, Nino


In questo caso, bisogna raggiungere 3, 7, 15, 31, 62, 125, 250 e 500
(chi parte dal 2 vince), facendo ogni volta N/2 ed eliminando
gli eventuali decimali.
Ciao, Nino

 strettamente minori del totale, la metà non c'entra :-(
Allora è ancora più facile.
Con una mossa non siamo in grado di passare da x a 2x, con due però possiamo
di raggiungere sia 2x che 2x+1, quale che sia il passaggio intermedio.
Questo in binario equivale ad aggiungere un bit a piacimento a destra di un
qualsiasi numero.
Per esempio, se il totale parziale fosse 26 (11010), il nostro avversario
con una mossa non potrà mai arrivare a 11010x, mentre noi lo possiamo fare
qualsiasi cosa faccia lui. Quindi possiamo aggiungere bit a piacimento, ergo
possiamo raggiungere qualsiasi target, una volta che riusciamo ad agganciare
la sequenza iniziale di bit.
Chi muove per primo può solo cominciare la sequenza con 11, il secondo
giocatore vince nel caso in cui l'espansione binaria del numero da
raggiungere cominci con 10. Quindi la discrimante la fa il secondo bit da
sinistra.
Per esempio, nel caso di mille, che in binario vale 1111101000 vince il
primo giocatore, passando per i parziali 11, 111, 1111, 11111, 111110,
1111101, 11111010, 111110100 e 1111101000.
Ciao, Silv:o)

 Ciao, Nino
Giusto, in pratica basta scrivere N in binario, poi se
N comincia con 11... vincerà il primo, altrimenti vince il secondo
giocatore.
La strategia per quello dei due che deve vincere è di portare il punteggio
al valore che in binario corrisponde alle prime cifre da sinistra di N,
aggiungendo una cifra ad ogni mossa:
Se N=1000, cioè 1111101000
il primo giocatore dovrà ottenere nell'ordine:
  3 = 11
  7 = 111
 15 = 1111
 31 = 11111
 62 = 111110
 125= 1111101
 250= 11111010
 500= 111110100
1000= 1111101000
Ciao
Andrea