Da ieri (v. il corto Accidenti ai leoni e agli gnu) mi era rimasta la voglia di risolvere un rompicapo decente!Oggi non avevo molto tempo perché alle 16:00 avevo un appuntamento dal dentista (una tragedia: ne scriverò in seguito!) così sono uscito di corsa dopo pranzo prendendo la bicicletta per raggiungere il centro e da lì procedere a piedi. Questi rompicapi infatti li posso affrontare solo mentre cammino perché con la bici sarebbero una distrazione troppo pericolosa…
Prima di partire mi sono cercato un nuovo problema: ci sono cinque sacchi, tutti in fila e numerati da 1 a 5, e un gatto che dorme ogni notte in un sacco diverso. Però si sposta solo in un sacco adiacente: cioè se dorme nel sacco 3 il giorno dopo potrà dormire solo nel 2 o nel 4; se dorme nel 5 il giorno dopo dormirà per forza nel 4.
La domanda è trovare un procedimento per individuare il gatto, sempre che sia possibile!
Dunque, dicevo, arrivato sui viali ho lasciato la bici e mi sono addentrato in centro a piedi pensando al problema. Per prima cosa mi sono ricordato che lo avevo già risolto qualche anno fa!
Questo in verità non mi ha aiutato perché ripetutamente, invece di concentrarmi su come risolverlo, mi distraevo involontariamente a tentare di ricordare come avevo fatto (senza riuscirci!). Insomma il sapere di averlo già risolto era più una distrazione che un aiuto…
La seconda cosa che mi è venuta in mente è che il gatto passa dai sacchi dispari ai pari e viceversa. Non mi sembrava di aver usato questo dato quando lo risolsi anni fa ma, avendo ormai fatto vari rompicapi, ho iniziato a notare subito questo tipo di dettagli…
Dopo poco però ho preso un gelato: ho continuato a mangiare camminando ma, anche qui per motivi di sicurezza, ho smesso di pensarci: da bambino rimasi traumatizzato quando mi cascò a terra il gelato dal cono e da allora ci sto particolarmente attento!
Sono poi arrivato al mercato delle pulci (dove mi sono affrettato a finire il gelato per non avere distrazioni) e mi sono messo a cercare il DVD o de “Il nome della rosa” o de “Il silenzio degli innocenti”: ho trovato il secondo che ho pagato 3€…
Sulla via del ritorno ho continuato a pensare pochissimo al problema ma piuttosto a come sistemare il DVD sulla bici. Come se non bastasse mi sono fermato anche ad assaggiare la schiacciata di un locale che mi era parso allettante…
Ritornato in bici non ci ho più pensato. Poi sono andato dal dentista dove ho aspettato tantissimo ma mi ero portato un libro da leggere.
Tornato a casa ero però molto agitato e così ho deciso di addolcire il mio dolore per le grane dentistiche andando a comprare delle caramelle di zucchero dette “ginevrine”. Però ci sono andato in bici fermandomi a 5-10 minuti di distanza dal negozio di caramelle. Comunque ho ripensato al rompicapo ma senza fare progressi.
Stasera ho scoperto di essere senza cena e così sono riuscito per andare a prendermi un kebab a un negozietto a 10 minuti di distanza. Sulla via del ritorno mi sono ricordato del rompicapo.
SCIUPATRAMA
Per prima cosa ho provato a semplificarlo: cosa succede se le scatole fossero solo 3? basterebbe controllare due volte di seguito la scatola 2 e al massimo al secondo tentativo vi troveremo il gatto.
Però già passando a 4 scatole non vedevo come fare progressi.
Ho notato che la cosa più difficile di questi problemi è staccarsi dall’ipotesi su cui stiamo lavorando per provarne una totalmente nuova: non so, per me è proprio uno sforza significativo.
Però, quando ormai ero vicino a casa, ci ho provato e sono tornato a pensare a come sfruttare l’idea che il gatto passa dalle scatole dispari a quelle pari e viceversa. Mi sono detto se controllo tutte le dispari al turno dispari e le pari al turno pari forse riesco a individuarlo? Ci ho pensato un po’ (perché infatti l’idea se non vi sembra chiara è perché non lo è!) e poi mi sono detto: “il gatto inizialmente può essere o in una scatola dispari o in una pari: supponiamo quindi che al primo turno sia in una scatola dispari…”
In questa ipotesi il gatto sarà o nella scatola 1, 3 o 5.
Controllo la scatola 1: se c’è ho finito, se non c’è al turno 2 sarà in una scatola pari (o la 2 o la 4).
Al secondo turno controllo la 2: se c’è ho finito, se non c’è allora era alla 4. Al terzo turno sarà quindi o nella scatola 3 o nella 5.
Al terzo turno controllo la scatola 3: se c’è ho finito, se non c’è allora era nella 5 (e al turno successivo tornerà per forza nella 4).
Al quarto turno controllo quindi la scatola 4: se c’è ho finito altrimenti significa che l’ipotesi iniziale, il gatto al primo turno in una scatola dispari era errata. Se l’ipotesi iniziale era errata allora significa che adesso il gatto è in una scatola dispari anziché pari e che quindi al quinto turno andrà in una scatola pari (o la 2 o la 4).
Al quinto turno controllo la scatola 2: se c’è ho finito altrimenti significa che era nella scatola 4 e che si sposterà nella 3 o nella 5.
Al sesto turno controllo quindi la scatola 3: se c’è ho finito, se non c’è allora era nella 5 e al turno successivo tornerà nella 4.
Al settimo turno apro la scatola 4 e sicuramente vi trovo il gatto…
Una volta trovata l’idea giusta questa soluzione l’ho pensata in pochi secondi, diciamo un minuto. Ma è sempre così: il problema è avere l’intuizione giusta, poi con quella è facile risolvere ogni problema…
Mi chiedo se sia possibile trovare una soluzione più veloce: però il problema non chiedeva di trovare la soluzione ottimale e io sono troppo pigro per cercare una soluzione non richiesta!
La sequenza di scatole da aprire è quindi:
1
2
3
4
2
3
4
Stona quell’1 iniziale… Mi chiedo se ipotizzando che il gatto sia inizialmente in una scatola pari si riesca a guadagnare un turno, vediamo:
2
3
4 allora è in dispari, quindi
2
3
4
Sì, sembrerebbe possibile risolvere il rompicapo in 6 turni nel caso peggiore!
Conclusione: un rompicapo carino!
PS: ecco il video da cui ho preso il problema: How To Solve The Hiding Cat Puzzle - Microsoft Interview Riddle
Nessun commento:
Posta un commento