lunedì 25 marzo 2013

Una pecora, in un campo, con un lato nero

Cosa dire del quesito che ho postato sabato, quello sulla trasformazione della parola "AILATI" in "ITALIA", seguendo certe regole? Per quanto mi riguarda, mi piace poco, perché non si può risolvere se non andando a tentativi.

Siamo sicuri? Non si può, o io non ci sono riuscito?

Ma vediamo cosa è successo in realtà.

La mia scuola era una sede per i giochi matematici della Bocconi. Tempo prima dello svolgimento delle gare arriva a scuola un bel pacco sigillato contenente i testi e le soluzioni, che l'insegnante responsabile per la scuola mette in cassaforte, al riparo da sguardi indiscreti. Sul foglio risposte era riportato questo risultato, per il suddetto quesito: 26.

Qualche giorno prima della data delle gare arriva un'email urgente che dice che c'è un errore nella risposta, quella corretta è 24. Bene, prendiamo nota.

Finalmente arriva il giorno delle gare, tutti i partecipanti sono nelle aule, la banda di impallinati di giochi matematici della quale faccio parte è chiusa in un laboratorio della scuola, pronta per correggere. Cominciano ad arrivare i primi fogli con le risposte: correggiamo, facciamo un doppio controllo, introduciamo i dati nel computer.

Tra gli impallinati di giochi ci sono anche dei giocatori (figli, studenti, amici). Questi strani personaggi prima partecipano alla gara, poi vengono a fare un salto dove siamo noi correttori e danno una mano anche loro (a volte vengono solo a mangiare, perché è chiaro che tutto ciò che sto raccontando è fatto allo scopo di fare bisboccia, ehm). La prima cosa che fanno, però, prima ancora di mangiare qualche fetta di torta, è controllare le risposte. Arrivato al famoso quesito, uno di loro dice: «ma no, 24? È sbagliato! Io ho dimostrato che con 22 passi ci si riesce».

Fermi tutti, ma come? Ricontrolliamo, dai. Il gruppetto di giocatori/correttori si mette davanti a un foglio e, con una fetta di torta in una mano e una matita nell'altra, tutti cominciano a ricostruire la sequenza di mosse.

E noi che facciamo? C'è gente che ha risposto 24, e a cui abbiamo dato buona la risposta. C'è altra gente a cui invece abbiamo dato sbagliata la risposta 22, che facciamo se è giusta? Chiamiamo i colleghi di Carpi, anche loro sede dei giochi, ma sono un po' indietro con la correzione e non si sono ancora posti il problema. Chiamiamo Milano direttamente, ci dicono che controlleranno, ma capiamo che sono un po' nel caos (comprensibilmente: sono la sede centrale, avranno ricevuto un sacco di telefonate). Per un momento arriva l'indicazione di dare buone entrambe le risposte, ma nel nostro laboratorio c'è la ribellione: o è giusta una, o è giusta l'altra. Poi anche i milanesi riescono a trovare un momento per ricontrollare tutto, e finalmente si decide che 22 è la risposta giusta.

Proseguiamo la correzione, facciamo le premiazioni, arrivederci a tutti.

Però, c'è un però. Lo spirito del matematico che vede mezza pecora nera in un campo aleggia su di noi: il quesito chiede chiaramente quale sia il numero minimo di passi. Come facciamo a essere sicuri che sia il minimo? Chi ha scritto il quesito lo sa? Perché un conto è trovare una soluzione in 22 passi, un altro è invece dimostrare che con meno passi non ci si riesce.

Quando arrivo a casa, chiedo a .mau. (che, pur essendo anziano pure lui, si diletta ancora a fare giochi matematici) se dalle sue parti hanno riscontrato gli stessi problemi. Lui personalmente no (il quesito era considerato troppo facile per la categoria Grande Pubblico, quella a cui lui appartiene), però mi racconta che  anche a lui hanno chiesto di controllare se effettivamente esistesse una soluzione in 22 mosse. La richiesta proveniva da un altro amichetto, giocatore pure lui, e pure lui aiutante nelle correzioni. Amichetto che io conosco solo attraverso internet, l'ho incontrato per la prima volta sulle pagine di Rudi Mathematici, con lo pseudonimo di Bramo Logicar. Mi dice .mau. che lui ha la soluzione definitiva del problema, e quindi gli scrivo per conoscerla. Come dicevo, mi piacciono le soluzioni. Vorrei sapere se dall'altra parte la pecora è nera.

8 commenti:

.mau. ha detto...

per completezza aggiungo che io ci ho provato per una decina di minuti e non ho trovato una soluzione né in 22, né in 24 né in 26 mosse.

Marco ha detto...

In sei anni che partecipo non era mai successa una cosa del genere, ovvero soluzioni che cambiano a gara ormai conclusa. Già il giorno dopo se ne parlava su Matem@ticamente (per chi è interessato ci sono tutti i quesiti con tutte le soluzioni, alche il procedimento del quesito 6 con i 22 passaggi passo passo).
Negli anni ci sono stati quesiti che andavano risolti "a tentativi", ma sempre con tentativi numericamente abbastanza limitati. Salendo con gli ipotetici tentativi minimi (22 son ben tanti), le combinazioni possibili aumentano enormemente e già da questo si doveva capire che non era un quesito ideale per i giochi matematici dove anche il tempo ha la sua importanza.
Comunque, tornando al "lato nero del campo", non c'è certezza senza dimostrazione. Rimane quindi il dubbio che i 22 passaggi non siano realmente il minor numero. M'era venuta quasi la voglia di impostare un brute force, ma anche scoprendo (improbabile) un numero di tentativi minore di 22 non si sarebbe trattato di dimostrazione e quindi niente certezza. Poi da Milano hanno ufficializzato il 22 e a quel punto non valeva più la pena di perderci tempo.
A parte questa situazione particolare, io comunque abolirei completamente quesiti da risolvere a tentativi; non ne vedo l'utilità logico-matematica.
Un saluto
Marco

zar ha detto...

D'accordo sul fatto che i quesiti da risolvere a tentativi non siano un gran che. Però non sono d'accordo sul fatto che un programma che analizza tutte le mosse non sia una dimostrazione. Ne parlo domani :-)

.mau. ha detto...

e io commenterò (positivamente) domani.

Marco ha detto...

"Un programma che analizza tutte le mosse"... e proprio qui potrebbe stare il problema: come facciamo ad essere certi che il programma abbia davvero preso in considerazione tutte le mosse?

La discussione sulla validità di una dimostrazione via 'puter è sempre accesa e gli schieramenti sono abbastanza arroccati sulle proprie idee. Proprio oggi è uscito questo articolo; potrebbe esserci qualche spunto per il tuo eventuale articolo.
Se ne riparla eventualmente domani.

zar ha detto...

Bé, leggendo il sorgente del programma, possiamo vedere se considera tutte le mosse oppure no. Dipende dal programma, e dipende dal problema.

Giuseppe Lipari ha detto...

In informatica si fanno spesso le dimostrazioni per enumerazione. Per esempio, il famoso "model checking" corrisponde (più o meno, eh) nell'enumerare (in maniera più o meno furba) tutti i possibili stati di un sistema per scoprire se certe proprietà sono vere oppure no. E funziona abbastanza bene, se le proprietà sono decidibili...

Marco ha detto...

Leggendo semplicemente il sorgente purtroppo non sempre è sufficiente; si può leggere quello che in qualche modo viene "previsto" ma non quello che non è stato considerato ed è proprio lì che sta la debolezza del codice. Il codice perfetto non esiste se non quando "appoggiato" a leggi matematiche o comunque proprietà decidibili ed enumerabili (come fa presente G. Lipari). Concordo comunque sul fatto che tutto dipende dalla tipologia di problema e dalle soluzioni che si mettono in atto.
Aspetto il tuo prossimo articolo: l'argomento è di quelli interessanti.