Gioco di squadra [1]

[orsoulx]

$ 20 $ cartellini, numerati da $ 1 $ a $ 20 $, vengono mescolati e disposti, in fila e col dorso rivolto verso l'alto, su un tavolo.
$ 20 $ giocatori, anche loro numerati da $ 1 $ a $ 20 $, sono chiamati, uno alla volta, davanti al tavolo. Il loro obiettivo è trovare il cartellino con il proprio numero. Per fare questo ne possono capovolgere fino a $ 10 $. Se un giocatore qualsiasi non trova il proprio cartellino, la squadra ha perso. Se lo trova, può cercare di facilitare il compito ai giocatori che lo seguiranno, riordinando i cartellini nella maniera che preferisce, senza sbirciare quali numeri riportano quelli non capovolti. L'arbitro provvederà, naturalmente, a rimetterli tutti col dorso verso l'alto ed a ripristinare la spaziatura iniziale . Qualsiasi forma di comunicazione fra i giocatori che hanno superato il loro turno e quelli che devono ancora affrontare la prova è impedita.
a) Qual è la strategia di squadra ottimale e quale probabilità di vittoria comporta?
b) Generalizzare il risultato a squadre di $ n $ giocatori, con la condizione che il numero di cartellini da capovolgere sia non superiore alla metà di $ n $.
Ciao
B.

[axpgn]

Ci provo, ho ben due strategie ...

Il primo sceglie la carta nella posizione corrispondente al suo numero e le altre nove a caso; se non c'è, ha finito, se c'è la mette nel posto giusto e fa lo stesso con le altre (se possibile); il secondo e gli altri fanno lo stesso escludendo però la carta nella posizione di chi li precedeva (se tocca a loro significa che gli altri hanno trovato quella giusta e l'hanno rimessa a posto, d'altro canto le condizioni poste non mi pare escludessero la possibilità che ciascuno conosca chi ha già giocato prima di lui).
Il calcolo della probabilità è un po' complicato ...

L'altra ...
Il primo sceglie le prime dieci carte (se ha un numero maggiore di dieci, lascia perdere la decima e solleva quella corrispondente al suo numero); il secondo sceglie la carta corrispondente al suo numero e poi quelle multiple di due escludendo quella relativa al suo predecessore; il terzo lo stesso ma quelle multiple di tre; il quarto quelle multiple di undici, poi tredici, diciassette e diciannove, gli altri a piacere ...

EDIT: Me n'è venuta in mente una terza: i giocatori scelgono a caso (tranne scegliere sempre la carta nella posizione del loro numero ed escludere quelle di chi li ha preceduti) però riordinano le carte in ordine progressivo (nelle posizioni disponibili)

Cordialmente, Alex

[veciorik]

L'ordine dei giocatori è noto ?

Se non lo è:

a) il primo mette i cartellini capovolti in ordine crescente e all'inizio della fila. Il secondo capovolge gli ultimi 10 e, sapendo quali erano i primi per esclusione, può metterli tutti 20 in ordine crescente.
Probabilità di vittoria $1/4=10/20*10/20$

La strategia vale anche per n generico, pari, se i capovolti sono esattamente la metà.

[orsoulx]

Allora; il titolo è numerato, perché questo quesito è propedeutico ad un secondo, che mi pareva troppo difficile da proporre direttamente. La strategia che ho pensato è, sicuramente, ottimale. Nel senso che posso escludere l'esistenza di un'altra con una probabilità di vittoria maggiore. La strategia in questione è anche indifferente all'ordine con cui vengono chiamati i giocatori. Due precisazioni:
1) il giocatore può capovolgere fino a $10 $ cartellini, anche nel caso che abbia trovato il suo con meno tentativi;
2) il numero riportato sui cartellini non capovolti, non si può 'sbirciare', ma questi possono comunque essere spostati qualora servisse.

@Alex:

la strada è buona: potrebbero esserci più strategie ottimali (sicuramente ve ne sono almeno due se i giocatori vengono chiamati ordinatamente), ma devono essere sistemate.
[ot]Se hai la soluzione 'originale' per il quesito dei briganti, perché non la posti?[/ot]

@Rik:

funziona, ma la probabilità di vittoria è migliorabile.

Ciao
B.

[axpgn]

Non avevo compreso che si potessero spostare anche quelli coperti ... quella di Rik mi pare una bella soluzione ...

[Pachisi]

Ho una strategia, ma non riesco a calcolare la probabilità.

Il giocatore 1 scopre la carta nella posizione 1 e nove altre a caso. Poi, mette ogni carta nella sua corrispondente posizione (eg: carta 7 in posizione 7, etc...). Poi, riordina le carte che non ha scoperto tra di loro (senza muovere quelle che ha scoperto). Il giocatore 2 scopre la carta nella posizione 2 e nove altre a caso, e poi ripete quello che fa il giocatore 1. Gli altri giocatori fanno la stessa cosa.

[veciorik]

Nuova strategia per il caso a). Con il calcolo sono in alto mare ma non ancora arenato.
Ore 01.33: Eureka.

Obiettivo di squadra è mettere i cartellini in ordine di numero da 1 a 20.
Ogni giocatore $g$ scopre come primo cartellino quello in posizione $g$.
Se non è il suo va alla posizione indicata dal cartellino che tiene in mano.
Mette lì, scoperto, quello che ha in mano e prende in mano l'ultimo trovato.
Ripete il ciclo finché trova il cartellino cercato $g$ che quindi va' al suo posto.
Quando lo trova passa alla posizione $g+1$, se non è già scoperta, altrimenti va' avanti alla prima ancora coperta.
Ripete il ciclo finché arriva a 10 scoperti. Mette il cartellino che ha in mano nel posto lasciato vuoto.
La probabilità di vittoria o sconfitta per il primo è comunque 1/2.
La probabilità che il primo giocatore trovi anche il cartellino 2 e lo metta a posto è 9/19.
Nei restanti casi 10/19 lo troverà di sicuro il secondo che, quindi, è assolutamente certo di trovare il suo cartellino.

Post scriptum 5/4 ore 00.10. Appena trovato il suo cartellino ne scopre uno ancora coperto: potrebbe essere già al suo posto oppure all'inizio di una nuova catena. Se era al suo posto non si può sapere se l'aveva messo lì il primo giocatore oppure se era già lì per caso. Qui il calcolo si complica, per me.

Per il terzo .... calcolerò con calma.

Post scriptum ore 01.33. La probabilità di vittoria della squadra è 1/2 perché tutti i giocatori dopo il primo troveranno certamente il loro cartellino, come già detto per il secondo. Per ognuno di loro ci sono due casi alternativi alla prima mossa:

[*:2z4uhu79]Il cartellino cercato non è al suo posto: in tal caso scopriranno e riordineranno altri cartellini oltre quelli già sistemati prima di trovare il proprio.[/*:m:2z4uhu79]
[*:2z4uhu79]Il cartellino cercato è già al suo posto: chi è di turno è OK alla prima mossa, alle successive può metterne in ordine altri oppure nessuno; quest'ultimo evento può capitare, nell'ipotesi peggiore, fino al decimo giocatore quando i primi 10 cartellini sono una permutazione dei primi 10 giocatori. In tal caso l'undicesimo dà inizio ad un nuovo giro e scoprirà tutti i successivi.[/*:m:2z4uhu79][/list:u:2z4uhu79]

[orsoulx]

Non utilizzate completamente l'informazione derivante dall'aver sistemato $ 10 $ cartellini al loro posto.
Il calcolo della probabilità nel caso (a) non presenta alcuna difficoltà.

@Pachisi:
che piacere! Un giovin studente in questo dopolavoro frequentato da pensionati con il vizio del gioco.
Ciao
B.

[veciorik]

Risolto il caso a).
Ho corretto il mio messaggio precedente.

[axpgn]

Dovrebbe essere così ...

Il primo scopre la carta che si trova nella posizione corrispondente al suo numero, se non è quella "giusta", la mette nel posto corretto e scopre quella che si trovava in quel posto e così via fino alla decima; nel caso scopra quella giusta prende a caso quella successiva e prosegue fino al decima.
Se gli è andata bene arriva il secondo che scopre anch'esso la carta nella "sua" posizione, se non è quella giusta significa che è una delle dieci carte NON toccate dal primo e quindi con la stessa procedura precedente le rimetterà tutte a posto e tutti gli altri sono a posto; se invece fosse quella giusta ne prenderà un'altra a caso e con la stessa procedura di prima rimetterà a posto quelle che gli capitano (anche nessuna); il terzo si troverà nella stessa situazione: se non trova quella giusta le rimette tutte a posto, se trova quella giusta mette a posto quelle che capitano; male che vada si arriva all'undicesimo che le rimette a posto tutte.
La probabilità è del $50%$ ?

Cordialmente, Alex

[veciorik]

Ho esagerato con dettagli sovrabbondanti.
Il primo giocatore non è obbligato a seguire una strategia nelle mosse, può andare a caso.
Basta che al termine delle 10 mosse lasci i cartellini al posto giusto.
Però se segue la strategia la soluzione è più elegante perché tutti i giocatori agiscono allo stesso modo e l'esecuzione può essere affidata ad automi.
Riepilogo:

[*:f3ag4z6v]definizione: un cartellino è al suo posto quando il numero scritto coincide con la posizione nella fila[/*:m:f3ag4z6v]
[*:f3ag4z6v]l'obiettivo della squadra è mettere tutti i cartellini al loro posto[/*:m:f3ag4z6v]
[*:f3ag4z6v]il primo giocatore scopre 10 cartellini e li mette a posto, non importa come[/*:m:f3ag4z6v]
[*:f3ag4z6v]il primo ha 10/20 = 1/2 di probabilità di trovare il suo cartellino che, in tal caso, va automaticamente a posto[/*:m:f3ag4z6v]
[*:f3ag4z6v]ogni altro giocatore scopre per primo il cartellino che occupa la posizione corrispondente al proprio numero di maglia[/*:m:f3ag4z6v]
[*:f3ag4z6v]poi obbedisce pedissequamente al cartellino appena scoperto: va alla posizione indicata, ci mette il cartellino che ha in mano e preleva quello che trova, e così via finché arriva al suo cartellino[/*:m:f3ag4z6v]
[*:f3ag4z6v]arriva di certo perché la concatenazione delle mosse non può mai ripassare per cartellini che sono già al loro posto e ogni catena si chiude su se stessa al massimo al decimo anello[/*:m:f3ag4z6v]
[*:f3ag4z6v]può esistere una sola catena con più di 10 anelli, che danneggerebbe soltanto il primo giocatore se ci incappasse alla prima mossa e seguisse la strategia automatica[/*:m:f3ag4z6v]
[*:f3ag4z6v]comunque non esiste nessuna strategia di gioco che possa aumentare la probabilità di successo del primo giocatore, se non bara.[/*:m:f3ag4z6v][/list:u:f3ag4z6v]

[orsoulx]

@Rik e Alex:
Strategia alternativa, applicabile solamente quando i giocatori vengono chiamati in ordine crescente:

1) il primo scopre dieci cartellini, trova $ 1 $ (probabilità $ 1/2 $) e ordina in ordine crescente i cartellini che ha trovato nei posti:
da $1 $ a $ 10 $, se ha scoperto anche il $ 2 $;
da $ 1 $ a $ 11 $ in caso contrario, inserendo al posto $ 2 $ uno di quelli non girati.
2) il secondo giocatore gira il cartellino al posto $ 2 $ e poi:
se ha trovato $ 2 $, gira gli ultimi e li ordina in ordine crescente;
altrimenti, gira gli ultimi nove (fra cui troverà sicuramente il $ 2 $, che sistema al suo posto) ed ordina i rimanenti.
3) tutti quelli che seguono troveranno il proprio numero in una delle posizioni $ 3, 11, 12 $:
se è in posizione $ 11$ non fanno nulla;
altrimenti, se è in posizione $ 3 $ lo portano in posizione $ 10 $ facendo scorrere in avanti quelli delle posizioni $ 4..10 $;
altrimenti, portano il loro cartello nella posizione $ 20 $ , facendo scorrere in avanti quelli delle posizioni $ 13..20 $.

Manca ancora il punto (b), per il caso meno semplice ( $ n $ dispari ) basta anche una valutazione spannometrica.
Ciao
B.