Qualche giorno fa mi ero cercato un nuovo problema da “portarmi dietro” per quando esco a spasso: «abbiamo un sacco con 101 monete: 51 autentiche e 50 false. Una moneta falsa pesa (come tutte le altre false) esattamente 1 gr in più o in meno di una autentica. Il solito guardiano ci dà una di queste monete presa dal sacco e ci chiede di stabilire se sia originale oppure falsa. A nostra disposizione abbiamo una bilancia digitale con due piatti che ci fornisce la differenza di peso fra questi. Possiamo usare la bilancia per un’unica pesata con qualsiasi sottoinsieme delle 101 monete come preferiamo.»Poi sono uscito ma, sfortunatamente, andavo alla pizzeria sotto casa e così ho potuto pensarvi solo pochi minuti. In questo caso però non avevo la minima idea di come fare: volevo essere logico ma non vedevo nessun passaggio intermedio alla soluzione richiesta (che è il punto di partenza).
E poi mi erano venuti dei dubbi sulla formulazione del problema:
1. Possiamo distinguere le monete false dalle autentiche dentro il sacco? Ovviamente no, altrimenti il problema sarebbe stato banale! Sarebbe bastato confrontare la moneta da identificare con una autentica e vedere se il peso era lo stesso o se differiva per 1 grammo…
2. Sappiamo il peso delle monete autentiche? Sapendo, per esempio, che una moneta autentica pesa 3 grammi (e le false quindi o tutte 2 o tutte 4 grammi) si poteva forse costruire delle specie di equazioni… Ma tornato a casa verificai che non abbiamo questa informazione.
SCIUPATRAMA
Il giorno dopo, rischiando grosso a causa della mia tendenza all’insonnia, ci pensai brevemente a letto. E qui feci, credo, un progresso.
Dall’esame di TAC (Teoria Algoritmi e Calcolabilità) ricordavo che la complessità teorica inferiore dell’ordinamento di N elementi è o(N): in altre parole per poter essere ordinati ogni elemento deve essere considerato almeno una volta.
Questo mi ha probabilmente suggerito la seguente riflessione: se la differenza fra una moneta autentica e una falsa è un grammo in più o in meno allora l’unica maniera per distinguere le false dalle autentiche è quella di pesarle tutte.
Per esempio supponiamo di pesare 10 monete e, grazie a qualche trucco diabolico, scopriamo che 6 pesano 10 grammi e le altre 4 pesano 9 grammi: come facciamo a sapere se le sei monete sono le false che pesano un grammo in più delle autentiche oppure se sono le quattro a essere false pesando un grammo in meno?
Ma fui bravissimo, oppure stanchissimo, e riuscii a evitare di pensarci e ad addormentarmi subito.
Il giorno successivo ogni tanto mi capitò di pensarci e cercai di stabilire cosa succedeva mettendo le 100 monete su un piatto e quella da identificare sull’altro. L’idea mi sembrava abbastanza sensata ma aspettavo di pensarci con calma durante una passeggiata…
Stamani ho cercato di spiegare il problema a mio padre con la relativa intuizione sul fatto che si doveva pesare sicuramente tutte le monete ma non sono sicuro di quanto mi abbia compreso…
Comunque mi ero organizzato per pensarci come si deve durante una passeggiata: avevo infatti deciso di prendere la bicicletta per avvicinarmi al centro ma di parcheggiarla da qualche parte e proseguire a piedi…
Già mi pregustavo questo piacevole divertimento ma, proprio per non avere dubbi sui dettagli, prima di uscire riapro il problema per rileggerne il testo e… delusione! ...mentre lo rileggo intuisco la soluzione!
Ovviamente smetto di pensarci ma ero decisamente sicuro di aver capito come fare…
Così vado verso il centro in bici e la lascio sui viali. Finalmente inizio a camminare e mi concentro sul problema: ma, come temevo, in appena 50 metri verifico che lo ho già risolto…
Forse riderete di me ma ero sinceramente deluso: tutto il mio divertimento che da giorni pregustavo era sfumato in pochi attimi… l’equivalente cerebrale di una eiaculazione precoce!
Allora mi viene un’idea: raggiungo una grossa libreria in centro, cerco un libro di problemi logici/matematici, ne scelgo uno e lo risolvo sulla via del ritorno!
Con questo incentivo raggiungo una libreria Feltrinelli dove però il commesso mi invia a un reparto dove non hanno niente che faccia al caso mio (io ero convinto invece che avrei avuto l’imbarazzo della scelta!). Fortunatamente alla libreria vicina trovo un librone pieno di problemini con delle belle illustrazioni: non so forse per bambini…
Fra questi scelgo il seguente:
PROBLEMINO BONUS (FACILE):
Usando solo il numero 5 arrivare al numero 11 in 8 operazioni.
Tornando al problema originario la soluzione che mi era venuta in mente era quella di mettere 50 monete su un piatto e 50 sull’altro, tenendo in mano la moneta da identificare.
Se la “mia” moneta è falsa allora sulla bilancia ci saranno 51 monete autentiche e 49 false; se invece è autentica sulla bilancia ci saranno 50 monete autentiche e 50 false.
Il punto è che nel primo caso le monete false saranno in numero dispari, nel secondo pari.
Ora come possiamo suddividere un numero di monete pari su due gruppi (piatti della bilancia)?
Sicuramente ce ne saranno un po’ nel primo piatto e un po’ nel secondo: diciamo N nel primo piatto e M (con M>N) nel secondo. Questo significa che N monete sul primo piatto ed N nel secondo si annulleranno fra loro e la differenza di peso sarà data dalle rimanenti sul secondo piatto: ovvero M-2N che sarà un numero pari (perché M+2N è pari per ipotesi, quindi possiamo scrivere M come 2*P e quindi 2P+2N = 2(P+N) che quindi è pari).
Se questo numero è pari allora sulla bilancia apparirà un numero di grammi (positivo o negativo non è importante) pari a 2*(il numero di coppie di monete false), quindi un numero di grammi le cui unità saranno 0, 2, 4, 6 o 8.
Se invece le monete false sono in numero dispari allora, tolte quelle che si annullano fra loro nei due piatti, significa che in un piatto ne rimarrà un numero ancora dispari.
In questo caso sulla bilancia apparirà un numero di grammi le cui unità saranno 1, 3, 5, 7 o 9.
Nel caso precedente la mia moneta sarà autentica, in questo falsa.
Graficamente (con "A" per le monete autentiche ed "F" per le false):
Caso con F in numero pari:
Piatto 1 - Piatto 2
A - A
A - A
...
A - A
A - F
A - F
F - F
F - F
...
F - F
Caso con F in numero dispari:
Piatto 1 - Piatto 2
A - A
A - A
...
A - A
A - F
A - F
A - F
F - F
F - F
...
F - F
La soluzione del problemino facile è invece facile…
Per strada avevo pensato (5x5+5x5+5)/5
Ma mentre scrivevo questo pezzo ho pensato a 5+5+5/5
Non so, forse arrivarci in esattamente 8 operazioni è più difficile?
No, perché per arrivarci con solo operazioni basta prendere la seconda soluzione e aggiungervi e sottrarvi 5 ripetutamente:
Cioè: 5+5+5/5+(5-5+5-5)
Bo, probabilmente era effettivamente un libro di problemi per bambini!
Conclusione: mi chiedo se il mio cervello abbia lavorato al problema della bilancia mentre non ci pensavo coscientemente e che, in questa maniera, appena ne ho riletto il testo la soluzione sia emersa spontaneamente. Secondo me è molto plausibile…
Dovrei scrivere un pezzo su come risolvo i problemi negli esami di intelligenza...
Nessun commento:
Posta un commento