Newsgroup: it.hobby.enigmi
Titolo: Problema originale di strategia dei giochi

Questo problema dovrebbe avere almeno un pregio, ossia dovrebbe essere
originale.
Se e' gia' passato stavolta mi arrabbio, perche' e' mio!
Ebbene consideriamo il gioco seguente. In una stricia di caselle lunga
n,
con n dispari altrimenti il gioco e' banale,
il gioco consiste nel porre un pezzo di domino (ossia un pezzo che
occupi
esattamente 2 caselle) in 2 caselle libere. Chi pone l'ultimo pezzo ha
vinto.
Esempio con striscia lunga 9
1 2 3 4 5 6 7 8 9, il primo giocatore pone il pezzo sulle caselle 3-4,
il secondo sulle
caselle 7-8, poi il primo in 1-2 e il secondo in 7-8, vince il secondo.
Esiste una strategia da seguire qualsiasi sia n, per cui la domanda e':
Con 37 caselle conviene iniziare, o giocare per secondi?
Siete in grado di trovare un strategia che valga per ogni n?
Indizi.
E' comunque un gioco riconducibile al nim.
Per chi non si ricorda il Nim e' quel gioco in cui si parte dalla
posizione
            !
        !   !   !
    !   !   !   !   !
!   !   !   !   !   !   !
e lo scopo e' prendere l'ultimo bastoncino. Esistono varie varianti (chi
prende l'ultimo
perde), ma questa e' conosciuta col nome Nim.
Ma la varieta' di tali giochi e' infinita, basti pensare al gioco del
100,
fatto sempre tra 2 giocatori che a turno devono sommare ad una cifra
un numero tra 1 e 10 compresi, e vince chi dice 100.
Il primo comincia dicendo un numero tra 1 e 10, e il secondo ci deve
sommare una quantita'
da 1 a 10 e cosi' via.
Ciao!!
Andrea   
visc...@hotmail.com
--
Posted from 
mta04-acc.tin.it
 [212.216.176.35]
via Mailgate.ORG Server - 
http://www.mailgate.org

originale.
Sei sicuro che questo gioco non e' in Winning Ways? :-)
(vedi 
http://www.mistral.co.uk/ghira/recmathslibri.html
)
Comunque...
facciamo i soliti calcoli
$g[0]=0;
$g[1]=0;
$g[2]=1;
%blank=();
for($n=3;$n<=40;$n++) {
    %seen = %blank;
	for($i=0;$i<=($n-2)>>1;$i++) {
		$seen{$g[$i]^$g[$n-2-$i]}=1;
		}
	$i=0;
    while($seen{$i}>0) {
    $i++;
    }
    $g[$n]=$i;
    print $n."  ".$i."\n";
    }
e vediamo che g(37)>0, allora 37 e' vincente.
visto che 35 e' perdente, una mossa corretta da 37 e' coprire le prime
due caselle. anche 28+7, 28+7, 24+11, 18+17 sono corrette.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
I am never forget the day I first meet great Lobachevsky. In one
word he told me secret of success in mathematics: Plagiarise.

Siete in grado di trovare un strategia che valga per ogni n?
ok. guardando la tabella dei valori Grundy per questo gioco, notiamo
che sembra "eventually periodic".
possiamo convincerci che e' davvero eventually periodic? si', perche'
facendo i calcoli a mano con strisce di carta avremmo:
parte iniziale ... parte periodico
parte periodico ... parte inziale
allungando tutto di un periodo, in mezzo appare solamente una copia in
piu' del blocco periodico, e agli estremi non cambia niente.
(spiegazione stringata, lo so. vedete Winning Ways per roba
piu' soddisfacente)
Allora, per giocare dobbiamo conoscere i i valori iniziali, e un
periodo:
0  0
1  0
2  1
3  1
4  2
5  0
6  3
7  1
8  1
9  0
10  3
11  3
12  2
13  2
14  4
15  0
16  5
17  2
18  2
19  3
20  3
21  0
22  1
23  1
24  3
25  0
26  2
27  1
28  1
29  0
30  4
31  5
32  2
33  7
34  4
35  0
36  1
37  1
38  2
39  0
40  3
41  1
42  1
43  0
44  3
45  3
46  2
47  2
48  4
49  4
50  5
51  5
52  2
53  3
54  3
55  0
56  1
57  1
58  3
59  0
60  2
61  1
62  1
63  0
64  4
65  5
66  3
67  7
68  4
69  8
70  1
71  1
72  2
73  0
74  3
75  1
76  1
77  0
78  3
79  3
80  2
81  2
82  4
83  4
84  5
85  5
86  9
87  3
88  3
89  0
90  1
91  1
92  3
93  0
94  2
95  1
96  1
97  0
98  4
99  5
100  3
101  7
102  4
103  8
104  1
105  1
106  2
107  0
108  3
109  1
110  1
111  0
112  3
113  3
114  2
115  2
116  4
117  4
118  5
119  5
120  9
gli ultimi 34 valori sono uguali al blocco precedente di 34, allora
siamo ok.
e per giocare basta conoscere i risultati fino a 86
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
We know Jesus must have been Italian for 3 reasons: he lived at home
until he was 30, he thought his mother was a virgin, and she thought
he was God.

Se e' gia' passato stavolta mi arrabbio, perche' e' mio!
Ok. Naturalmente, bisogna controllare su Winning Ways.
Il tuo gioco si chiamerebbe 0.07 nella notazione di WW per i
"subtraction games"
Peggio, e' discusso esplicitamente col nome "Dawson's Kayles" su
pagina 92 del primo volume, ed i suoi valori sono usati per analizzare
altri giochi in capitoli 8,13,15 e 16.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
Anvedi oh che roba!

Ok, rileggendo il capitolo di Winning Ways su queste cose, mi rendo
conto che bisogna controllare fino a 170qualcosa per essere sicuri che
sia cosi', ma comunque la mia risposta e' corretta. periodo 34 da
50qualcosa in poi. allora bisogna conoscere i valori G fino a
80qualcosa.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
Volemo er verde!

Non sapevo pero' che si chiamasse 0.07!!
Un gioco interessante e' 0.6. Non so se e' stato risolto. (un singolo
gettone non puo' essere tolto. qualsiasi gruppo di due o piu' gettoni
puo' essere diminuito di 1 e lasciato in 1 o 2 gruppi.)
vedi 
http://www.mistra.co.uk/ghira/recmathslibri.html
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
XYZZY

 wrote:
% dovresti leggerlo. e anche "Games of No Chance", visto che
% aggiorna/estende Winning Ways. "On Numbers and Games" non
% e' necessario: Winning Ways ha tutte le cose importanti di ONAG
Tranne la storiella di JHWH CNWY :-)
.mau.

Tranne la storiella di JHWH CNWY :-)
vero. ma al giorno d'oggi, ONAG deve essere difficilissimo da trovare.
(sono molto contento di aver comprato WW e ONAG nel 1985 quando erano
facili da trovare...)
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
I have a spelling chequer. It came with my pea sea. It plane lee marques for my
revue miss steaks eye can knot sea. I ran this poem threw it. I'm sure yore pleased
two no. It's letter perfect in its weigh - my checker tolled me sew.

 wrote:
% >% Winning Ways ha tutte le cose importanti di ONAG
% 
% >Tranne la storiella di JHWH CNWY :-)
% 
% vero. ma al giorno d'oggi, ONAG deve essere difficilissimo da trovare.
Ho il sospetto di si`.
Ma sono certo che ?manu* andra` in biblioteca, mi fotocopiera` la parte
rilevante di ONAG, e me la spedira`, ovviando all'errore che feci nel 1985.
Vero? :-)
.mau.

 
  Anvedi oh che roba! Stavolta lo dico io :-)
Ebbene, non ho mai letto winning ways, anche se mi sono ripromesso piu'
volte di farlo.
Ora che mi ci fai pensare, avevo sentito parlare che in esso si faceva
riferimento
alle Grundy functions. Io mi ero riproposto di pensare a qualcosa simile
al Nim
che avesse uno sviluppo con le funzioni di Grundy. L'ho fatto in una
tesina un 8 anni fa.
Non sapevo pero' che si chiamasse 0.07!!
Congratulazioni per la rapidita' comunque e grazie per l'esaurientissima
risposta.
Ciao
Andrea    
visc...@hotmail.com
--
Posted from [208.163.206.2]
