Newsgroup: it.hobby.enigmi
Titolo: Gino e Gina - Ricomincio da otto

Provo a riprendere il problema dei Gini, dimenticando (quasi) tutto
quello che è stato trovato finora.
L'idea è quella di valutare il vantaggio che può derivare a Gino per il
fatto di poter puntare di volta in volta conoscendo i risultati dei
lanci precedenti, ossia di poter interpretare le informazioni in modo
diverso da caso a caso.
Forse la cosa non porterà risultati utili, o magari sto dicendo in altre
parole quello che è stato già esaminato, ma non escluderei del tutto che
qualcuno possa trarne spunto per trovare qualcosa di buono.
Parto dalla soluzione che nel primo post è stata definita "banale", cioè
Gino punta a caso sui primi otto lanci, indovinandone mediamente
quattro, poi gioca sicuro gli ultimi otto secondo le indicazioni di
Gina: 0=T, 1=C.
In questo modo si hanno mediamente 12 vincite, con minimo di 8.
Applico una variante distinguendo due casi:
A) Se nei primi otto lanci è presente un segno dominante, allora Gina
indica questo segno col primo bit. Gino gioca per otto volte quel segno,
garantendosi un minimo di 5 vincite e un massimo di 8. I rimanenti 7 bit
indicheranno i lanci dal nono al quindicesimo, e sono altri 7 punti
sicuri, mentre per il sedicesimo lancio Gino punta a caso, vincendo in
media 0.5 punti.
Sono ora garantiti 12 punti.
B) Se nei primi otto lanci non esiste un segno dominante, ossia ci sono
4T e 4C, Gina riserva gli otto bit agli ultimi otto lanci.
Gino gioca le prime otto volte come indicato dal primo bit, vincendo
comunque quattro volte. Poi incamera gli ultimi otto lanci, e quindi ha
ancora 12 punti garantiti.
Questo è possibile perché dopo otto lanci Gino sa, in base ai risultati,
se si trova nel caso A o nel caso B, e si regola di conseguenza per gli
altri otto.
Nel caso A gioca a partire dal secondo bit, nel caso B ricomincia dal
primo.
Salvo errori, per questa variante trovo una vincita media di 12.73+
contro i 12 del caso base, con 12 vincite garantite comunque contro le
8.
-----------------------
Una variante ancora più favorevole si avrebbe dividendo i primi otto
lanci in quattro coppie, a cui si assegnano (eventualmente) i primi
quattro bit.
Se la prima coppia è formata da segni uguali, il bit indica quel segno
garantendo due punti. Se i segni sono diversi, si vince un punto, ma il
bit rimane disponibile per la coppia successiva.
Quindi Gina utilizza da 0 a 4 bit per indicare le coppie con segni
uguali, e da 8 a 4 per indicare i segni dei lanci dal nono in avanti.
Vediamo per esempio una sequenza e le informazioni corrispondenti (usare
caratteri fissi)
TC TT CC TC  T C C T C T T C
   0  1      0 1 1 0 1 0
In base al primo 0 Gino gioca TT per la prima coppia (1 punto).
Visti i risultati della prima coppia, sa che il bit non è stato ancora
utilizzato, e gioca TT nella seconda coppia (2 punti).
Ora sa che il bit è stato utilizzato e prende in considerazione il
secondo bit, gioca CC nella terza (2 punti).
Anche il secondo è utilizzato, Gino considera il terzo bit e gioca
TT nella quarta coppia (1 punto).
Finite le coppie, e utilizzati due bit, Gino sa che i bit dal terzo in
avanti si riferiscono ai primi sei lanci del secondo ottetto (6 punti)
Gioca a caso gli ultimi due lanci (1 punto in media).
Per questa variante si hanno 12 punti garantiti con media di 13.
I risultati sono ancora lontani da quelli già ottenuti con altri
approcci, ma mi pare che il vantaggio rispetto al caso banale di
partenza sia comunque interessante.
Qualche idea per sfruttare meglio la cosa?
ciao
paolo
P.S.
L'idea mi è nata partendo da questa considerazione:
Un bit mi garantisce due punti su tre lanci, oppure tre su cinque.
Cosa si può fare su un numero pari di lanci?

 Cosa si può fare su un numero pari di lanci?
Credo che non si possa fare niente di meglio che dare l'indicazione sui
primi n-1 lanci e lasciare indovinare l'ultimo. La cosa viene confermata
anche dal calcolo del massimo teorico (potendo fornire un solo bit di
informazione):
lanci    vincita media
1    1
2    1,5
3    2,25
4    2,75
5    3,4375
6    3,9375
7    4,59375
8    5,09375
9    5,73046875
10    6,23046875
11    6,853515625
12    7,353515625
13    7,966308594
14    8,466308594
15    9,071044922
16    9,571044922
La differenza tra la vincita media con un numero di lanci pari rispetto al
valore precedente è sempre di 0,5 (l'ultimo bit da indovinare).
Ciao :-)
Giorgio

Leggendo il tuo post, mi sono convinto che la tua idea fosse geniale ed ho
voluto migliorarla.
Ho ridotto il problema ad un modello più semplice ma equivalente: 4 lanci e
2 bit di informazione, in modo tale che, una volta risolto il problema,
l'avrei potuto estendere al nostro caso.
Dopo un po' di elucubrazioni e conti, ho visto che il tuo metodo è
inefficace. Ora cerco di spiegarti perchè, e dimmi se mi sbaglio.
Con 4 bit possono succedere le seguenti cose:
a) 1° Coppia Uguale - 2° Coppia Uguale
b) 1° Coppia Uguale - 2° Coppia Eterogenea
c) 1° Coppia Eterogenea- 2° Coppia Uguale
d) 1° Coppia Eterogenea- 2° Coppia Eterogenea
Nel caso (a) il tuo metodo garantisce 4 vittorie su 4.
Nel caso (b), con il primo bit indovino esattamente i primi 2 lanci, con il
secondo che considero come informazione di coppia uguale perchè ancora non
ho il risultato dei lanci 3 e 4 indovino solo 1 lancio su 2. Nota che non
riesco a sfruttare l'informazione che abbiamo sapientemente nascosto nel
nostro codice e che ottengo 3 risultati utili su 4, tanti quanti il caso
peggiore di un metodo naif qualsiasi.
Considero ora il caso (c): considero il primo bit come informazione di
coppia uguale, indovino 1 solo lancio su 2 e deduco di dover utilizzare
ancora il primo bit come bit di informazione di coppia per i lanci 3 e 4.
Così facendo, indovino esattamente i lanci 3 e 4. Nota che anche in questo
caso ho ottenuto 3 risultati utili su 4 (come nel caso peggiore di un metodo
naif) e che solo a gioco terminato ho potuto costatare la validità della
informazione che abbiamo aggiunto in questo caso.
Nel caso (d), considero il primo bit come bit di informazione di coppia
uguale, gioco ed indovino solo 1 lancio su 2. Come nel caso precedente, mi
ostino ad utilizzare il primo bit per pronosticare i lanci 3 e 4, ma in
questo caso ottengo 1 solo risultato utile su 2. Anche in questo caso,
riesco ad accorgermi della informazione aggiuntiva inserita nel codice solo
a giochi fatti, ed in più ho ottenuto un risultato peggiore rispetto a
quello pessimo di un metodo naif.
(Inciso: il metodo naif che ho usato per il confronto è il seguente. Il
primo bit a 1 indica che nei primi 3 lanci si ha maggioranza di "testa", a 0
indica la maggioranza di "croce". Il secondo bit a 1 indica che nel quarto
lancio è uscito "testa", a 0 indica che è uscito "croce". Questo metodo
garantisce nel caso peggiore 3 risultati utili su 4.)
Per i problemi di complessità 4, come quello esposto, il tuo metodo risulta
essere poco efficace. Ma che dire per problemi di complessità maggiore, ad
esempio 16, come quella del quesito iniziale? Secondo me, si può dimostrare
in modo ricorsivo che si ha lo stesso inconveniente. LA differenza consiste
nel fatto che l'informazione nascosta viene accumulata e non utilizzata per
più tempo e comunque lo si capisce solo alla fine del gioco.
Secondo me, bisognerebbe in qualche modo anticipare l'utilizzo
dell'informazione nascosta, per non perderla poi alla fine. Un possibile
metodo potrebbe essere questa variante alla tua idea: ogni bit di codice
indica sempre la maggioranza di "testa" o "croce" nella prossima coppia, in
caso di risultati diversi tra loro il bit considerato indica il risultato
del lancio successivo alla coppia. Nel caso alla fine rimanesse da
indovinare un lancio singolo, il successivo bit ne indicherebbe
semplicemente il risultato.
Per un problema di complessità 4, si avrebbero nel caso peggiore 3 risultati
utili su 4. Per un problema di complessità 16, si avrebbero nel caso
peggiore 11 risultati utili su 16 sfruttando solo 6 bit di codice. Anche
questo metodo che fa economia di spazio ma non è buono...
Ho visto giusto? Adesso scrivo un'altro post in cui illustro un'altra idea
che stavo considerando, in modo da non rendere troppo lungo e noioso questo!
Ciao,
  Stefano

Io pensavo di sfruttare il poter puntare un po' per volta nel modo che
segue.
Suddivido i 16 lanci in gruppi da 3 in questo modo:
1° Gruppo: risultati dei lanci dall'1 al 3
2° Gruppo: risultati dei lanci dal 3 al 5
 ecc. ecc. fino a
7° Gruppo: risultati dei lanci dal 13 al 15
I primi 7 bit indicherebbero la maggioranza di "testa" o di "croce" in ogni
gruppo, visto che in ogni gruppo di cardinalità dispari c'è per forza un
segno in maggioranza. L'8vo bit rappresenterebbe semplicemente il risultato
dell'ultimo lancio.
Credevo che la bontà di questo metodo consistesse "nell'ereditare" parte di
informazione dal gruppo precedente, in modo tale da indovinare anche alcune
triplette non composte tutte da segni uguali.
Dopo averci ragionato un po' mi sono reso conto che questo codice era
semplicemente ridondante, infatti in un problema di complessità 8 ad
esempio, il caso peggiore consisteva in 5 risultati utili su 8 invece di 6
su 8 del metodo naif.
Ho riportato solo questa idea nella speranza che possa far venire qualche
buona idea a qualcuno.
Ho pensato anche di formare gruppi di cardinalità dispari ma diversa tra
loro:
1° Gruppo: risultati dei lanci dall'1 al 3
1° Gruppo: risultati dei lanci dall'1 al 5
   ecc. ecc.
Ma si dimostra che il risultato così ottenuto è del tutto equivalente al
risultato dei gruppi con cardinalità costante dispari.
Ad onor di cronaca, il metodo naif ottimo per questo tipo di problemi di
complessità 2^n e 2^(n-1) bit a disposizione per la codifica consiste in:
(per n=4 si hanno 16 lanci da indovinare e 8 bit da codificare)
1) partizionare l'insieme dei risultati in due sottoinsiemi di cardinalità
dispari
2) per il primo sottoinsieme di cardinalità 2^(n-1)-1 si usano altrettanti
bit per indicare il risultato di ogni elemento ad esso appartenente
(garantiti 2^(n-1)-1 risultati utili su 2^(n-1)-1 )
3) per il secondo sottoinsieme di cardinalità 2^(n-1)+1 si usa il solo bit
rimasto per indicare maggioranza di "testa" o di "croce". (nel caso peggiore
si hanno così 2^(n-2)+1 risultati utili su 2^(n-1)+1 )
Nel complesso si hanno nel caso peggiore 2^(n-1)-1+2^(n-2)+1 = 3 * 2^(n-2)
risultati utili su 2^n.
(Per n=4, il primo insieme è formato da 7 elementi, il secondo da 9 e si
hanno 12 risultati utili su 16 nel caso peggiore).
Speriamo che sia d'aiuto!
Salve,
  Ste