Esploratori

[axpgn]

1)
Dopo un'intera giornata in perlustrazione nei boschi dell'Alberta, Jack e la sua squadra sono in difficoltà nel ritornare al campo base.
Sono giunti ad una piccola radura da cui si dipartono quattro sentieri e sono a conoscenza del fatto che uno di questi conduce a casa in venti minuti di cammino.
Ma non hanno idea di quale sia!
Non possono comunicare con la base, né hanno mezzi tecnologici a disposizione; l'unica possibilità è quella di percorrerli e vedere dove portano.
Purtroppo manca un'ora al tramonto, dopodiché, senza luce, diventa estremamente pericoloso muoversi, di fatto sarebbero bloccati.
Ma c'è unaltra complicazione per Jack: egli ha il sospetto, più che fondato, che due dei componenti della sua squadra siano dei sabotatori e possano mentire, quindi inaffidabili; però non sa chi siano tra i suoi otto compagni.

Qual è la strategia che Jack deve sicuramente adottare per riportare alla base sè stesso e tutta la sua squadra?


Cordialmente, Alex

[axpgn]

Nessuno?

[Bokonon]

Sono stato sul posto ed ho ricostruito come è andata realmente.
I due sabotatori sono partiti con gruppi diversi ed hanno ucciso i compagni per poi darsi alla macchia.
Uno è arrivato a casa l'altro è stato divorato dai lupi.
Jack è stato costretto a tirare la monetina e i lupi hanno fatto nuovamente festa.

Questo è ciò che accade quando ti impunti

[axpgn]

No, no, c'è pure una quarta situazione

[axpgn]

Siccome inizio a provare un po' di compassione per questi esploratori che girano da un mese , penso sia giunta l'ora di dargli la soluzione ...

Se ci sono cinque potenziali bugiardi, la squadra deve essere composta da almeno $17$ esploratori.
Jack va da solo su un percorso mentre sugli altri vanno in sei su due percorsi e cinque sul rimanente.
Se Jack trova quello giusto, finito, altrimenti ecco come valutare le risposte ...
Se in nessun gruppo c'è disaccordo interno, ignorare il gruppo da cinque.
Se c'è disaccordo interno ad un solo gruppo, ignorare quel gruppo.
Se c'è disaccordo interno in più di un gruppo, allora in ciascuno di questi gruppi contare la minoranza (nel caso tre contro tre, la minoranza è tre).
Questo è il minimo numero di potenziali bugiardi in quel gruppo.
In ogni gruppo dove il numero delle risposte della maggioranza è maggiore di cinque meno il totale del minimo numero di bugiardi di tutti gli altri gruppi, affidarsi alla risposta della maggioranza.
Con meno, ci sono almeno due percorsi con solo dieci persone, se cinque mentono, non c'è soluzione che tenga.

Comunque, i nostri esploratori non si fanno intimorire per così poco e sono già pronti per un'altra (e ultima) missione

4) Supponiamo che la squadra di Jack sia composta da soli $4$ compagni di cui due potenziali bugiardi ma il tempo a disposizione sia di $100$ minuti invece che $60$.
Qual è la strategia giusta da adottare ?


Cordialmente, Alex

[andomito]

Prima esplorazione i 4 compagni da una parte (percorso 1) e Jack da una altra (percorso 2)
Se jack trova il bersaglio torna e porta tutti sul sentiero 2 in 60'.
Resta il caso che il percorso 2 è escluso
Se i 4 hanno una maggioranza essa è vera.
. Se indica che hanno trovato il bersaglio si va tutti sul sentiero 1 (in 60'),
. altrimenti resta il caso che sono esclusi sia 1 e che 2.
. Quindi Jack porta tutti sul percorso 3 e poi decide (se ha trovato il target ha finito il 60', se no si va tutti sul 4, arrivando al target in 100').
Resta il caso in cui i 4 non hanno una maggioranza, in tal caso Jack manda i due che dicono che il percorso 1 è sbagliato sul sentiero 3, lui va sul sentiero 1 e i due che dicono che il percorso 1 è giusto li lascia alla base (o li porta con sé, o li manda su sentieri a caso).
. se ha jack trova che il sentiero 1 è giusto torna e porta tutti al target in 100' (e sa che quelli che ha mandato sul sentiero 3 sono traditori).
. Se ha trovato che il sentiero 1 è errato sa che i due esploratori che ha mandato sul sentiero 3 sono veritieri e dunque ascolta le loro indicazioni per portare tutti in salvo in 100'.

A questo punto la domanda è d'obbligo, perché il quesito è con 4 esploratori (con due traditori) e non 2 (con un traditore)?
Forse con 4 si può fare di meglio?

con la soluzione proposta la probabilità che jack becchi il target al primo colpo è del 25%
In ogni altro caso ci metteranno 100' (se i due traditori vogliono almeno rallentare il gruppo in ogni caso dopo la prima esplorazione mentiranno).
Quindi il tempo medio della soluzione è di 90'.
Si può fare di meglio?
Se mando tre esploratori sul sentiero 1 e uno sul 3 dopo il primo giro (escluso che Jack abbia trovato il target) avrò questi casi
i 3 sono concordi e hanno trovato la soluzione (1 è giusto) [caso irrealistico perché il traditore negherà]
i 3 sono concordi e non hanno trovato la soluzione (1 è errato). In questo caso la soluzione è o il sentiero 3 o il 4. Se jack porta tutti su uno dei due ha una probabilità (12,5%) di portare tutti in salvo in 60'
i 3 sono discordi e 2 dicono di aver trovato la soluzione, e inoltre
il quarto dice di non averla trovata. In questo caso la soluzione è o il sentiero 1 o il 4. Se jack porta tutti su uno dei due ha una probabilità (12,5%) di portare tutti in salvo in 60'
o di averla trovata. In questo caso la soluzione è o il sentiero 1 o il 3. Se jack porta tutti su uno dei due ha una probabilità (12,5%) di portare tutti in salvo in 60'
I 3 sono discordi e 1 dice di aver trovato il target, e inoltre
il quarto dice di non averlo trovato. in questo caso jack deve andare e tornare dal sentiero 1 per capire chi dei tre mente e mandare i due concordi e il quarto compagno sul sentiero 4. Se jack trova il target torna indietro e porta tutti in salvo. Se no da retta alla maggioranza di quelli che ha mandato sul sentiero 4 per scegliere tra questo e il sentiero 3. In ogni caso ci mette 100'
o di averla trovata. in questo caso tra quelli che dicono di aver trovato il target c'è un traditore, quindi i due concordi sono leali. Escluso quindi il sentiero 1 la soluzione è tra sentiero 3 e 4. Jack porta tutti su uno di essi avendo una probabilità (12.5%) di concludere in 60'.
Facendosi i conti dei casi si sovrappongono (dipendono dalla scelta di un mentitore) e quindi jack può portare a casa il gruppo in 60' mediamente il 50% dei casi.
Quindi il tempo medio si riduce a 80'.

L'unico rischio è di formare (con il 50% di probabilità) un gruppo con maggioranza di traditori, che potrebbero sopraffare il compagno e darsi alla macchia. Comunque in tal caso Jack (con il superstite leale) si salverebbe mediamente in 70'

[axpgn]

Bravo! Molto bene!

"andomito":Forse con 4 si può fare di meglio?

Non so cosa intendi per "meglio" perché l'obiettivo è quello di trovare una strategia che riporti a casa tutti nel tempo limite prestabilito e questa esiste e l'hai trovata, la media delle percentuali di successo non la trovo significativa (IMHO).
L'unica differenza alla tua soluzione è che è sufficiente mandare un solo esploratore sul percorso 3 al secondo giro

Cordialmente, Alex