Indovina il seme

[Martino]

Ho un mazzo di 40 carte da briscola. Quattro semi (denari, coppe, spade, bastoni) e dieci carte per ogni seme (da 1 a 10).

Il gioco è questo: scartare una carta dopo l'altra cercando di indovinarne il seme. Supponiamo di giocare in modo perfetto (vale a dire, ricordando le carte scese) assegnando una qualche preferenza ai semi, per esempio denari - coppe - spade - bastoni, in caso di parità di semi scesi.

La mia domanda è: qual è il numero medio di carte indovinate se si gioca in modo perfetto?

Procedendo a caso il numero medio è ovviamente 10, ma giocando con la memoria delle carte scese dovrebbe essere apprezzabilmente più alto.

Naturalmente uno può riformulare la cosa dicendo che le carte sono i numeri da 1 a 40 e la cosa da indovinare è la classe resto modulo 4. Io ho una idea di cosa potrebbe essere ma lo devo ancora dimostrare.

[Rggb]

Interessante...

Una domanda: perché quella precisazione sulla preferenza dei semi? Supponi di avere le tue 40 carte divise in 10 blu, 10 rosse, 10 verdi e 10 gialle, che motivo c'è di sapere - per dire - che le rosse vengono "prima" delle gialle? Oppure non ho capito, spiegami.

[Martino]

Una domanda: perché quella precisazione sulla preferenza dei semi? Supponi di avere le tue 40 carte divise in 10 blu, 10 rosse, 10 verdi e 10 gialle, che motivo c'è di sapere - per dire - che le rosse vengono "prima" delle gialle? Oppure non ho capito, spiegami.

E' per evitare di andare a caso una volta che i semi scesi sono alla pari. Per rendere la cosa algoritmica, insomma. Se tu non dessi una preferenza ai semi non sapresti (per dire) da che seme partire.

Io alla prima carta dico "denari". Se viene denari, alla carta successiva devo scegliere uno dei semi più probabili (che sono coppe, spade e bastoni) e scelgo coppe perché viene prima di spade e bastoni nella mia preferenza. Se non facessi così alla seconda carta dovrei andare a caso e il procedimento non sarebbe univocamente determinato dalla sequenza in cui sono poste le carte.

Spero di essere stato chiaro

[Rggb]

Chiarissimo: in questo modo garantisci la perfezione. Il ganzo è che - così a occhio - anche se non hai seme preferito e quindi a parità di carte uscite procedi sempre a caso, direi che il numero medio è lo stesso

Sto pensando ad una soluzione - solo pensando, per adesso niente carta&penna: mi viene in mente una sequenza di potenze...

[DajeForte]

Bel problema; ti dico subito che la soluzione è ancora lontana.

Qualche considerazione.

Se vogliamo calcolare il numero medio di carte azzeccate la struttura di preferenza è irrilevante questo perchè la probabilità che tu azzecchi la carta non dipende da quello che dici ma da quello che è uscito;
serve soltanto a dare una struttura completamente determinata nella nostra selezione.

Se ragioniamo estrazione per estrazione sicuramente si individuano le prime \( \displaystyle {4} \) probabilità che sono: \( \displaystyle \frac{{10}}{{40}}\ \frac{{10}}{{39}}\ \frac{{10}}{{38}}\ \frac{{10}}{{37}} \). Il problema arriva ora.
La quinta estrazione potrà avere probabilità di azzecarla \( \displaystyle \frac{{9}}{{36}} \) se nelle prime quattro ho avuto \( \displaystyle {4} \) semi diversi (la prob è \( \displaystyle \frac{{{{\left(\matrix{{10}\\{1}}\right)}}^{{4}}}}{{{\left(\matrix{{40}\\{4}}\right)}}} \)), mentre è \( \displaystyle \frac{{10}}{{36}} \) con il complemento di quella.
Da un punto di vista logico si potrebbe continuare a ragionare in questa maniera; il problema è che risulta essere molto oneroso da un punto di vista computazionale (vengono una cosa tipo un centinaio di probabilità). Si dovrebbe trovare una formula in funzione dell'estrazioni effettuate e del valore massimo che un seme può possedere (che aumenta al crescere delle quaterne strazioni), se uno vi riuscisse poi lo fa fare al computer.

Il risutato atteso comunque migliora perchè iterando questa logica abbiamo che la probabilità di azzecare l'estrazione i-esima è maggiore di \( \displaystyle \frac{{{\left[\frac{{{40}-{i}}}{{4}}\right]}+{1}}}{{{40}-{i}+{1}}} \) (con la quadra intendo la parte intera), cioè nelle prime quattro al numeratore abbiamo sempre \( \displaystyle {10} \); dalla 5 alla 8 abbiamo o \( \displaystyle {9} \) e così via. Con la probabilità limitante che ho scritto sopra si considera la strada più pessimistica ovvero che ogni \( \displaystyle {4} \) carte mi escono tutti semi diversi.
Con questo si conclude che il valore atteso è maggiore di (se non ho commesso errori di calcolo) \( \displaystyle {11.966} \) circa, che però è una bela sottostima; pensa infatti all'ultima carta e quella viene prob \( \displaystyle {1} \); per la penultima la limitazione da un mezzo ma se sono dello stesso seme è uno.

Queste diciamo sono le prime impressioni che ho avuto, te che idee hai?

[Martino]

Io ho avuto qualche idea ma devo elaborare meglio quello che ho pensato. Sto partendo da un caso facile: 4 carte e 2 semi. Qui il numero medio risulta \( \displaystyle 2.8\bar{3} \) . Con 4 carte e 4 semi il numero medio è \( \displaystyle 2.08\bar{3} \) .

Diciamo che n=40 è il numero di carte e k=4 è il numero di semi. Indichiamo con S l'insieme di tutte le possibili sequenze delle n carte, e data una sequenza s (cioè un elemento di S) chiamiamo \( \displaystyle i_p(s) \) il numero di carte indovinate nella sequenza s con preferenza p (una "preferenza" è come sopra: un ordine dato ai semi). Dobbiamo calcolare il numero

\( \displaystyle M(n,k):=\frac{1}{n!} \sum_{s \in S}i_p(s) \) .

Per fare questo potrebbe risultare utile osservare che detto P l'insieme delle preferenze (ha \( \displaystyle k! \) elementi) si ha

\( \displaystyle \frac{1}{k!} \sum_{p \in P} \frac{1}{n!} \sum_{s \in S}i_p(s) = \frac{1}{n!} \sum_{s \in S}i_p(s) = M(n,k) \) .

In particolare si ha \( \displaystyle M(n,k) = \frac{1}{n!} \sum_{s \in S} \frac{1}{k!} \sum_{p \in P} i_p(s) \) . Quindi anziché mediare sulle sequenze direttamente uno potrebbe tentare di mediare prima sulle preferenze e poi sulle sequenze. Questo dovrebbe semplificare il problema.

Comunque come ho detto ci devo pensare bene ancora.

[Umby]

Il caso peggiore è stato descritto da Daje (per ogni gruppo di 4 carte, 4 semi diversi).
In questa condizione abbiamo la speranza di indovinare circa 12 carte (concordo con il 11,966 di daje) (anzichè 10 - il 10 inteso come 1/4 per 40 carte, ovvero in caso di reimmissione).

Il migliore dei casi è quello che le prime 30 escono solo 3 semi, in questa situazione abbiamo una speranza di indovinare circa 23,5 carte.

Tra questi due "limiti" tutte le altre combinazioni.
Non dovrebbe essere difficile simulare con il pc, tutte le varie combinazioni, cosi' da trovare un valore medio.

[Rggb]

Non dovrebbe essere difficile simulare con il pc, tutte le varie combinazioni, cosi' da trovare un valore medio.

Fatto. Una prima simulazione mi fornisce (circa) \( \displaystyle {n}={13.37} \) ovvero 13 come numero medio.

[DajeForte]

Non dovrebbe essere difficile simulare con il pc, tutte le varie combinazioni, cosi' da trovare un valore medio.

Fatto. Una prima simulazione mi fornisce (circa) \( \displaystyle {n}={13.37} \) ovvero 13 come numero medio.

Sono curioso di sapere come hai costruito la simulazione

[Rggb]

Con 4 carte e 4 semi il numero medio è \( \displaystyle 2.08\bar{3} \) .

Calcolato direttamente, "a mano" per capirci, o tramite la tua (abbozzo di) idea?

Comunque, il mio simulatore non dovrebbe avere errori poiché trova lo stesso risultato... oppure abbiamo sbagliato entrambi lo stesso calcolo

Sono curioso di sapere come hai costruito la simulazione

Eccolo qui.

Codice: Seleziona tutto

// carte.c 1.0.1    by RGGB    10-AUG-2010, 11-AUG-2010    (C) none
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
                     
#define N_LOOPS 10000
#define DBG
#define N_CARDS 40
#define N_SEEDS 4

int main(int argn, char *argv)
{
   double avg;      // media (calcolata, non intera)
   int tot,      // totale semi azzeccati in tutte le giocate
       deck[N_CARDS],   // Il mio mazzo di carte
       seed[N_SEEDS],   // I semi usciti nelle giocate
       mySeed,      // Che seme "gioco"
       min,      // Quale seme e' minimo
       i, j, k;

   // Messaggio di inizio (?)
   printf("\nSimulazione di un gioco matematico di carte.");
   srand((int) getpid());

   // Ciclo esterno per quante simulazioni voglio generare
   printf("\nInizio di %d simulazioni...", N_LOOPS);
   tot=0;
   avg=0.0;
   for (i=0; i < N_LOOPS; i++)
   {
DBG      if (!(i%1000)) printf(".");

      // Imposta i totali semi mescolati
      k=N_CARDS/N_SEEDS;
      for (j=0; j < N_SEEDS; j++) seed[j]=k;

      // Mescola le carte
      for (j=0; j < N_CARDS; j++)
      {
         while(1)
         {
            //k=4*random()/RAND_MAX;
            k=rand()%N_SEEDS;
            if (k >= 0 && k < N_SEEDS && seed[k] > 0)
            {
               // Carta correttamente mescolata
               deck[j]=k;
               seed[k]--;
               break;
            };
         };
      };
DBG      if (!(i%1000))
DBG      {
DBG         printf("\nMazzo corrente:\n");
DBG         for (j=0; j < N_CARDS; j++) printf("%d", deck[j]);
DBG      };

      // Imposta i totali estratti
      for (j=0; j < N_SEEDS; j++) seed[j]=0;

      // "Si gioca"
      for (j=0; j < N_CARDS; j++)
      {
         // La mia scelta: quello minore
         mySeed=0;
         min=seed[0];
         for (k=1; k < N_SEEDS; k++)
         {
            if (min > seed[k]) { mySeed=k; min=seed[k]; };
         };

         // Verifico se la mia scelta e' indovinata
         if (mySeed == deck[j]) tot++;

         // Comunque incremento semi usciti
         seed[deck[j]]++;
      };
   };
   printf("\nfine.");

   // Stampa risultato
   printf("\nTotale %d indovinate su %d simulazioni, con %d carte e %d semi.",
                         tot,             N_LOOPS,            N_CARDS,   N_SEEDS);
   avg=(double) tot / (double) N_LOOPS;
   printf("\nLa media di indovinate per giocata di %d carte e' %f\n\n",
                                                        N_CARDS,    avg);
};//(main)


Non fate caso ai "DBG"

EDIT: piccole modifiche al codice, ora è di uso più generale.