Menu
Le soluzioni del 18 ottobre 2021 a cura di Fabio Ciuffoli
Ieri mattina abbiamo proposto un gioco sulla Prova a Conoscenza Zero con diverse ipotesi di soluzione. Presentiamo di seguito le nostre proposte di soluzione.
Premio Abel e la Prova a Conoscenza Zero – soluzione
LA PEN DRIVE RUBATA. In un ufficio dove lavorano 100 persone è stata rubata una Pen Drive. I due capiufficio, Andrea e Dario, hanno un’idea abbastanza chiara di chi sia il ladro, ma nel timore che stiano pensando a persone diverse, nessuno dei due è disposto a dichiarare il sospettato. E’ possibile verificare se entrambi sospettano della stessa persona, senza rivelare alcuna informazione nel caso in cui i sospettati non coincidessero?
In sintesi si chiede se Andrea e Dario possono concordare un modo per determinare se possiedono le stesse informazioni, senza rivelarle reciprocamente nel caso in cui non lo posseggano.
Forniamo alcuni spunti per la riflessione. Andrea non può condividere nulla con Dario che possa identificare il suo sospettato, ad esempio non può dire: “Il mio sospettato arriva tardi il lunedì”, poiché rivelerebbe alcune informazioni su quella persona. Un’altra procedura non accettabile sarebbe rivolgersi a un amico comune, di cui entrambi si fidano. Andrea e Dario potrebbero scrivere, ciascuno su un proprio foglio, il nome o il numero in codice della persona sospettata e consegnarli all’amico comune. Se questo amico dice che i nomi o i numeri sono gli stessi allora i sospettati coincidono. Se fossero diversi, né Andrea né Dario saprebbero i rispettivi sospettati. Anche questa opzione non è soddisfacente. In primo luogo, non è detto che esista un amico comune, ovvero un verificatore indipendente e veritiero. Inoltre, ancora più importante, entrambi rivelano informazioni a questo amico comune. Il punto centrale di questo esercizio è di non rivelare alcuna informazione a nessuno. Anticipiamo che ci sono diverse soluzioni, ognuna con punti di forza e di debolezza.
SOLUZIONE. Come anticipato, il problema si presta a più soluzioni. Ne presentiamo tre con i relativi punti di forza e di debolezza.
1. Password e computer. Andrea cambia una delle sue password, per qualsiasi sito web, con il nome del sospettato. A Dario viene chiesto di accedere a quel sito web con la parola del suo sospettato. Se entra, significa che ha digitato lo stesso nome. Se non entra, significa che non ha digitato lo stesso nome. Punti di forza: molto facile da realizzare. Punti di debolezza: si possono fidare di un computer?
2. Prenotare un volo. Andrea chiama una compagnia aerea e prenota un volo con il nome del sospettato. Dario chiama la compagnia aerea e chiede di annullare la prenotazione del nome del suo sospettato. Se gli rispondono che non c’è alcuna prenotazione con quel nome, allora i nomi dei sospettati non corrispondono. Punti di forza: divertente e ingegnosa. Punti di debolezza: vengono fornite informazioni alla Compagnia Aerea.
3. Le 100 tazze. Andrea e Dario concordano una numerazione da 1 a 100 degli impiegati. Vengono poi allineate 100 tazze identiche in modo che ciascuna si trovi nella posizione contrassegnata da 1 a 100. Andrea e Dario prendono 100 foglietti di carta identici e scrivono SI’ su un foglietto e NO sui restanti 99, poi li piegano in modo da non vedere cosa c’è scritto. Ora collocano i loro foglietti nelle tazze avendo cura di mettere il SI’ nella tazza posizionata sul numero della persona sospettata e i foglietti con il NO nelle 99 tazze restanti. A questo punto si riorganizzano le tazze, in modo che nessuno sappia a che numero corrispondano. Infine si aprono i foglietti e se i due SI’ vengono trovati nella stessa tazza, allora i sospettati sono gli stessi. Se non si trovano due SI’ nella stessa tazza, le persone sospettate sono diverse. Punti di forza: semplice, non coinvolge terze parti. Punti di debolezza: approvvigionarsi di 100 tazze uguali; fidarsi del processo di randomizzazione; avere sangue freddo, quando si mette il foglietto con il SI’ nella tazza.
A lunedì prossimo.
In questa pagina vengono pubblicati giochi matematici, logici e di ragionamento ogni 15 giorni il lunedì in mattinata.
Siamo sempre alla ricerca di nuovi giochi e nuove proposte. Se vuoi suggerirne uno, scrivici un’e-mail a:
blog.giochi@prismamagazine.it
Fabio Ciuffoli è autore di diversi libri sul problem solving e i giochi logici e matematici, il più recente è Giochi matematici e logici.
PRISMA: pubblicazione mensile registrata presso il Tribunale di Milano (N. 235 del 19.09.2018).
Tutti i diritti di proprietà artistica e letteraria sono riservati.
L’editore è a disposizione di eventuali detentori di diritti che non sia stato possibile rintracciare.
Mateinitaly srl – p.iva 09164520968 – Corso Vercelli 27 – 20144 Milano (MI).
2 risposte
Riporto altre proposte di soluzione interessanti:
Riccardo Bernardini: Calcolano l’SHA512 del nome del sospettato. Se gli hash sono uguali stanno pensando alla stessa persona, altrimenti no. È praticamente impossibile invertire l’hash, ma con 100 persone uno dei due potrebbe calcolare tutte le hash per scoprire la persona sospettata dall’altro.
Diciamo che funziona se nessuno dei due vuole attivamente trovare ciò che pensa l’altro.
Riccardo Bortolotto: Tubo nero vuoto capienza 100 palline, Dario ne mette x , Andrea 100-y , se riempiono il tubo con 100 palline esatte allora x=y=numero assegnato a sospettato
Vincenzo Sicari a Riccardo Bortolotto: Non funziona! A, conoscendo il proprio y, riesce facilmente a ricavare x. E lo stesso vale se è D, che vuole fare il furbo. (Chi verifica deve essere incorruttibile, ad esempio una app).
Per accettare alcune soluzioni, occorre definire se i due capiufficio si comportano correttamente, rispettando le regole stabilite oppure possono trasgredire le regole per trarre un vantaggio proprio. Ad esempio, nel caso della lampadina se uno dei due capiufficio mette l’interruttore on in modo scorretto per verificare se anche l’altro capufficio ha messo on. In questo casi come è stato scritto:
“Diciamo che funziona se nessuno dei due vuole attivamente trovare ciò che pensa l’altro.”.
Mi sono arrivate tante proposte di soluzione, alcune bizzarre altre molto complicate e altre ancora troppo semplici, che non rispettano le condizioni del problema. Vorrei segnalarne alcune. Ad esempio Giovanni Battista Scambia
“C’e una lampadina con due interruttori lungo il cavo, entrambi gli interruttori devono essere on affinché la lampadina si accenda. A ognuno dei due viene affidato un interruttore e non hanno modo di vedersi. Vengono elencati i 100 nomi e ognuno dei due accende l’interruttore quando viene detto il nome che sospetta. Se la lampadina non si accende mai sospettano di persone diverse”