Wishful Thinking
Il mese scorso ci sono state le finali nazionali dei Campionati di Giochi Matematici, come sempre ospitati in Italia dalla Bocconi. Il vostro affezionato blogger non è andato benissimo, essendosi classificato tredicesimo nella categoria Grande Pubblico (dai 21 anni in su) per avere sbagliato l’ultimo problema. Ma non è delle mie performance che vi voglio parlare, bensì della tecnica che ho usato per risolvere il penultimo problema, che vi allego qui sotto per comodità.
Con 2012 pietre formate due mucchi, e scrivete il prodotto del numero di pietre contenute nel primo mucchio moltiplicato per il numero di pietre del secondo mucchio. Dividete poi uno dei due mucchi in due nuovi mucchi e scrivete il prodotto dei numeri di pietre contenute rispettivamente in questi nuovi mucchi. Dividete ora uno dei tre mucchi che avete ottenuto, scrivete il prodotto, ecc. ecc. fino a quando otterrete 2012 “mucchi” composti in realtà da una sola pietra. Quanto vale la somma dei 2011 prodotti che avete scritto?
Come si potrebbe risolvere questo problema? Per prima cosa, se nel 2012 trovate un problema in cui c’è il numero 2012 potrebbe essere il caso che la soluzione del problema sia generale, e che sia stato scelto 2012 semplicemente perché i matematici hanno un perverso senso dell’umorismo. Non avendo nessuna idea di quale possa essere il risultato, un risolutore di problemi dati ai giochi matematici probabilmente immagina che il problema si può risolvere per induzione. Le dimostrazioni per induzione hanno due guai, come scrissi altrove: sono noiose e soprattutto occorre sapere in anticipo qual è il risultato per dimostrarlo. Sul primo guaio non si può fare nulla, sul secondo in genere si tira a indovinare provando con valori piccoli.
Se avessimo solo due pietre, le possiamo dividere solo come 1 e 1; la “somma” del singolo prodotto è 1. Pertanto S(2)=1. Se avessimo tre pietre, le possiamo dividere solo come 1 e 2 (prodotto 2), e poi siamo costretti a dividere il mucchio da 2 (prodotto 1), e quindi S(3)=2+1=3. Con quattro pietre ci sono due possibilità: due mucchi di 2, con un prodotto 4 a cui sommare 1 e 1 che si ottengono dall’ulteriore loro suddivisione, oppure un mucchio di 1 e uno di 3, con prodotto 4 a cui sommare il 3 ottenuto dalla suddivisione del mucchio di tre. In ogni caso, S(4)=6. Abbiamo 1, 3, 6: proviamo a immaginare che i valori siano dati dai numeri triangolari (la successione 1, 3, 6, 10, 15… dovrebbe essere notissima a chiunque faccia giochi matematici), e quindi la nostra supposta formula per S(n) sia data da n(n−1)/2. Dimostriamolo per induzione, sapendo che il primo passo l’abbiamo già fatto qui sopra.
Il mucchio di n+1 elementi può venire diviso in due parti di k+1 e n−k elementi, con k che va da 0 a n-1. La somma di tutti i prodotti sarà pertanto data da (k+1)(n−k)+S(k+1)+S(n−k); il primo prodotto e la somma di quelli che si otterranno coi due mucchietti. Vi risparmio tutti i conti che fortunatamente eliminano tutti i fattori contenenti un k, ricavando alla fine n2/2 − n/2, che effettivamente è proprio S(n+1). Ergo, la risposta cercata è S(2011)=2023066.
Beh, non penserete mica che io abbia risolto il problema in questo modo, vero? :-) (L’ho dovuto fare adesso per scrivere questo post: dura la vita del divulgatore). Durante la gara, ho sfruttato una delle tecniche più potenti per la risoluzione di giochi matematici: il wishful thinking, appunto.
Come funziona il wishful thinking? Semplice. Quello che dovevo risolvere non era un problema vero e proprio, ma un esercizio dato come problema a una gara di giochi matematici. Quando l’ho visto, ho pensato “Cribbio, ma le suddivisioni si possono fare in un numero enorme di modi!” Ma ho anche pensato “Se è stato dato come problema, vuol dire che la risposta è sempre la stessa, qualunque sia la successione di suddivisioni che scelgo. Ma allora posso sceglierne una “comoda”, togliendo una pietra per volta; i “prodotti” saranno i numeri da 2011 scendendo via via fino a 1, e la loro somma sarà 2011×2012/2. Tempo totale per la risoluzione: due minuti.
Questo metodo è barare? No. Chiaramente se mi fosse stato chiesto di dimostrare che ogni successione di suddivisioni dà quel risultato, come potrebbe capitare in un compito in classe, allora non avrei affatto risolto il problema: ma qui mi veniva solo chiesta la soluzione, ed ero in un contesto ben specifico (una gara di giochi matematici, ripeto: non un problema che mi sono inventato o mi è capitato tra le mani modellizzando un’esperienza della vita reale). In amore, in guerra e nelle gare di giochi matematici tutto è lecito!
Leave a comment