Newsgroup: it.hobby.enigmi
Titolo: Dare i numeri

Con il caldo di questi giorni puo' capitare che qualcuno dia i numeri; per
questo propongo un gruppo di enigmi, senza nemmeno essere sicuro che esista
in tutti i casi una soluzione possibile. Comunque, provateci e buon
divertimento.
Premessa comune a tutti i 5 giochi:
I giochi si svolgono tra due giocatori, A e B, entrambi perfetti logici.
Ciascuno dei due deve scegliere un numero intero positivo (quindi diverso da
zero), con le limitazioni indicate volta per volta. I numeri scelti sono
scritti su un biglietto e verificati alla fine del gioco. Quindi ciascuno fa
la scelta senza conoscere quella dell'avversario.
Le scelte NON sono casuali; ciascuno agira' secondo una strategia, valutando
anche quella che ritiene sara' la strategia dell'avversario; non e' comunque
da escludere che la strategia migliore risulti in qualche caso proprio la
scelta casuale.
Tutti i giochi sono a somma nulla, cioe' l'importo vinto da un giocatore e'
uguale a quello perso dall'altro.
Gioco n.1
A sceglie un numero dispari tra 1 e 99. B sceglie un numero pari tra 2 e 98.
Dopo aver fatto la scelta, B deve indovinare quale dei due numeri sia il
piu' grande.
Se indovina, riceve da A 1 Euro, se non indovina, paga ad A una cifra X.
Domande:
Quali sono le strategie dei due giocatori?
Quale deve essere il valore di X perche' il gioco sia equo?
Gioco n.2
Come il gioco n.1, ma senza limiti superiori nei numeri da scegliere. Cioe':
A: numero dispari>=1
B: numero pari >=2
Stesse domande del gioco n.1
Gioco n.3
Ciascuno dei due giocatori sceglie un numero intero tra 1 e 100.
Se i numeri sono entrambi dispari o entrambi pari, vince chi ha scelto il
numero maggiore.
Se un numero e pari e l'altro dispari, vince chi ha scelto il minore.
Domanda:
Quale e' la strategia dei due giocatori?
Gioco n.4
Come il gioco n.3, ma senza limite superiore per la scelta. Cioe' ciascuno
deve scegliere un numero intero positivo.
Stesse domande del gioco n. 3
Gioco n.5
Ciascun giocatore sceglie un numero intero positivo.
Se entrambi i numeri sono pari, B riceve da A un Euro.
Se un numero e' pari e l'altro e' dispari, B paga ad A una cifra X.
Se entrambi i numeri sono dispari, il gioco e' nullo e si ricomincia.
Domande:
Quali sono le strategie dei due giocatori?
Quale deve essere il valore di X perche' il gioco sia equo?
ciao
paolo

fara' vincere praticamente al 100 % : ...
In questo caso devo dire che mi hai spiazzato; credevo che il gioco
risultasse insolubile, nel senso che portasse ad una serie infinita di
ragionamenti del tipo: A pensa che B pensa che A pensa......
Il tuo ragionamento invece mi sembra esatto, da "perfetto logico";
complimenti!
Cosi' sui due piedi, mi viene in mente una possibile variante,
Sadicamente la propongo:
Gioco n.6
Come il gioco n.5, ma:
Se i numeri sono entrambi pari, B vince 1 Euro
Negli altri casi (pari+dispari o dispari+dispari) A vince X Euro.
in questo caso non c'e' possibilita' di pareggio, come il golden gol!
ciao
paolo

qualsiasi numero dispari e 49,5 un qualsiasi numero pari.
Rispondo con un certo ritardo perche' in questo periodo non ho avuto molto
tempo per seguire il NG, ne' per approfondire il problema.
Con un'analisi affrettata mi pare che le tue considerazioni vadano bene se
l'avversario sceglie a caso. Ma se anche l'avversario fa le tue
considerazioni, c'e' una probabilita' maggiore (anche se di poco) che giochi
dispari, quindi dovrai scegliere un numero dispari basso o un numero pari
alto; cioe' non tutti i numeri darebbero le stesse probabilita'.
Se poi l'avversario fa anche questo secondo livello di ragionamento, non ho
idea di cosa possa succedere. Credo che alla fine si arrivi a concludere che
la cosa migliore sia una scelta del tutto casuale.
ciao
paolo

Quale e' la strategia dei due giocatori?
Ok. Questo si dovrebbe fare con la programmazione lineare, algoritmo
del simplesso, ecc. Ma non ricordo come si fa, allora per il momento
ecco una soluzione molto lenta e iterativa....
La "strategia" dei due giocatori deve essere le probabilita'
con cui sceglgono i numeri. La strategia sara' uguale per i due
giocatori, visto che il gioco e' simmetrico.
Allora, quale caratteristica possiede la strategia migliore?
Questa: anche se sai che il tuo avversario la sta usando, non ti aiuta.
Al massimo puoi pareggiare.
La tecnica seguente puo' essere usata anche in giochi non-simmetrici, ma
spiego solamente la versione simmetrica.
Al turno 1 giochiamo tutti e due una mossa qualsiasi. diciamo 1.
al turno n giochiamo la mossa che ci da' maggiore probabilita'
di vincere contro la distribuzione di mosse vista in turni 1,...,n-1
la distribuzione converge a quella giusta!
ecco un programma in perl:
for ($i=1;$i<=100;$i++) {
  for ($j=1;$j<=100;$j++) {
  $payoff[$i][$j]=pay_func($i,$j);
  #print "$i $j $payoff[$i][$j]\n";
  }
}
sub pay_func {
if ($i==$j) {
 return 0;
 } elsif ($i%2==$j%2) {
  return $i>$j?1:-1;
  } else {
    return $i<$j?1:-1;
  }
}
$n=1;
$f[1]=1;
while (1) {
$max=-2;
$move=0;
for ($i=1;$i<=100;$i++) {
$expect=expected();
if ($expect>$max) {
 $max=$expect;
 $move=$i;
 }
}
$n++;
$f[$move]++;
print "$n $max $move\n";
#print_table();
}
sub expected {
$val=0;
for ($j=1;$j<=100;$j++) {
$val+=$payoff[$i][$j]*$f[$j]/$n;
}
return $val;
}
sub print_table {
for ($i=1;$i<=99;$i+=2) {
$prob=$f[$i]/$n;
print "$i $prob";
$temp=$i+1;
$prob=$f[$temp]/$n;
print "   $temp $prob\n";
}
print "\n";
}
ad ogni iterazione, stampa il numero dell'iterazione, il valore della
migliore mossa possibile contro un avversario che gioca casualmente una
mossa scelta fra quelle precedenti, e la mossa stessa. come vedrete,
il valore della mossa migliore tende a scendere lentamente.
fate girare la cosa per molte iterazioni, magari facendo un "print_table()"
ogni tanto. se la distribuzione e' perfetta, il valore della mossa migliore
e' 0. (se ci fosse una mossa con valore >0, allora la strategia non sarebbe
la migliore :-))
c'e' qualcuno in area molto bravo con la programmazione lineare, o
a risolvere 100 equazioni simultanee in 100 incognite? quasi sicuramente
sarebbe piu' veloce del metodo che uso qui.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
You mean, you'll put down your rock, I'll put down my sword, and
we'll try to kill each other like civilized people?

Ok. Era quasi troppo ovvio.
La strategia migliore per gioco 3 e' giocare un numero fra 1 e 99,
tutti con probabilita' 1/99. Non giocare mai 100.
Questo si verifica abbastanza facilmente.
con f[1]=...=f[99]=1, n=99 nel mio programma
expect(i) = 0 per ogni i da 1 a 99, ed e' <0 per i=100.
Allora e' la soluzione.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
A hollow voice says "PLUGH"