backup del Post

Basta saperlo…

Lo so, è estate, ma non fa poi così caldo: insomma, potete anche lavorare un po’. Eccovi due problemi matematici: come fareste per risolverli?

• Quante sono le stringhe binarie – quindi composte di 0 e 1 – B_n di lunghezza n che non contengano all’interno due cifre 1 consecutive? Per esempio, 000101 è valida, mentre 001101 no.
• Quanti sono i sottoinsiemi S_n dell’insieme {1, 2, …, n} in cui non ci sono mai due numeri consecutivi? Per esempio, con i numeri da 1 a 6 il sottoinsieme vuoto {} e {1,3,6} sono validi mentre {2,3,5} no, perché ci sono 2 e 3.

 
Visti così, i due problemi sembrano piuttosto ostici: d’altra parte questa dovrebbe essere la situazione tipica di quando ci si trova di fronte a un problema. Certo che se un’anima pia ci dicesse “Dimostrate che il numero di stringhe B_n è dato dalla formula blablabla” sarebbe tutta un’altra cosa, vero? Devo fare l’anima pia? Massì, su: leggete qui sotto, se non volete fermarvi a risolverlo completamente per conto vostro.

Per la cronaca, ho trovato questi due problemi nel libro di Martin Erickson Pearls of Discrete Mathematics, come una noticina sul fatto che i numeri di Fibonacci spuntano dove meno uno se lo aspetta. In pratica, data la successione definita come

 F₀=0,
 F₁=1,
 F_n+2=F_n+1+F_n

abbiamo che sia B_n che S_n sono pari a F_n+2. Uno dei due risultati è anche dimostrato nel testo, il secondo no: ma questo non è così importante, visto che una volta che si capisce come dimostrarne uno si arriva direttamente al secondo.

Abbiamo dunque un punto di partenza piuttosto importante. Onestamente, un Vero Matematico non avrebbe nemmeno avuto bisogno di questo aiutino, perché si sarebbe messo a contare a manina il valore delle due successioni per n piccolo, e da lì avrebbe intuito la formula. Mettiamoci subito a fare i conti, allora!

Per B_n, la tabella è la seguente:
– B₀=1: per le mirabolanti proprietà dell’insieme vuoto, c’è un solo modo di avere una stringa di zero caratteri, e sicuramente essa non contiene due cifre 1 consecutive.
– B₁=2: le stringhe sono “0” e “1”.
– B₂=3: le stringhe sono “00”, “01” e “10”, visto che “11” è da cassare.
– B₃=5: alle tre stringhe qui sopra possiamo aggiungere a destra uno 0 e un 1, ma “011” è da togliere. Le stringhe sono quindi “000”, “001”, “010”, “100”, “101”.
– B₄=8: lascio al lettore la facile verifica :-)

Per gli S_n, la tabella è la seguente:
– S₀=1 per le stesse ragioni di cui sopra (di insiemi vuoti ce n’è uno solo, {});
– S₁=2: i sottoinsiemi sono {} e {1};
– S₂=3: i sottoinsiemi sono {}, {1}, {2};
– S₃=5: i sottoinsiemi sono {}, {1}, {2}, {3}, {1,3};
– S₄=8: i sottoinsiemi sono {}, {1}, {2}, {3}, {1,3}, {4}, {1,4}, {2,4}. (E non dite che non sono bravo, stavolta ve li ho scritti tutti, e anche nel modo migliore per dimostrare la proprietà!)

Occhei, supponiamo che di riffa o di raffa siate riusciti a intuire qual è la formula da dimostrare, e quindi abbiate fatto metà del lavoro. Generalmente, per dimostrare una formula generale per ogni n, il sistema più “naturale” è quello di usare l’induzione. Naturale tra virgolette, perché se uno matematico non è non gli verrebbe mai in mente, e anche se è un matematico usare l’induzione è sempre un modo per nascondere il fatto che non sa assolutamente qual è il significato intrinseco del problema e si rifugia nelle trasformazioni algebriche che si possono fare senza azionare neuroni se non per controllare che i conti siano giusti. Ma con Fibonacci c’è un’altra via, che sotto sotto è sempre induzione ma è un po’ meno scollegata dalla realtà: quella di dimostrare direttamente che vale la relazione indicata sopra, che cioè F_n+2=F_n+1+F_n. Detto in altro modo, si cerca di associare a tutti gli elementi di ordine n+2 un elemento di ordine n+1 oppure uno di ordine n, senza lasciarne da parte nessuno; la relazione si ottiene così immediatamente.

Nel primo caso, immaginiamo di avere una stringa binaria di lunghezza n+2: essa può terminare solo per 00, 10, oppure 01. Bene. Raggruppiamo i primi due casi, e otteniamo che la nostra stringa può terminare per 0 oppure per 01. Beh, le stringhe binarie di lunghezza n+2 che terminano per 0 e che non hanno due 1 consecutivi sono evidentemente B_n+1, e quelle che terminano per 01 e non hanno due 1 consecutivi sono B_n; i casi n=0 e n=1 li abbiamo provati a mano, e quindi siamo a posto. Nel secondo caso, il sottoinsieme dei numeri da 1 a n+2 può non contenere n+2 (e in quel caso vanno bene tutti gli elementi di S_n+1) oppure, se contiene n+2, allora non deve contenere n+1 (e in quel caso vanno bene tutti gli elementi di S_n). Di nuovo, aggiungendo i casi 0 e 1 trattati a mano sopra, abbiamo riscoperto la formula di base di Fibonacci. Notate come in entrambi i casi, seguendo tra l’altro uno dei dettami della combinatorica, abbiamo effettivamente contato gli elementi dei nostri insiemi: una dimostrazione insomma costruttiva.

Morale della storia? Che nella risoluzione di problemi matematici (che è cosa ben diversa dal fare matematica, ricordatevelo… ma che comunque qualche punto in comune ce l’ha) il Vero Matematico sa come cercare un’ipotesi facendo un po’ di prove a manina, e che per certi tipi di ipotesi (nel nostro caso, la successione di Fibonacci) ha nel suo Opportuno Manuale qualche tecnica standard, che allo studente tipico sembra tanto una magia ma non lo è affatto.

Post Scriptum: naturalmente un Vero Matematico non avrebbe mai dimostrato la seconda proprietà. Non perché l’avrebbe “lasciata come esercizio allo studente”, ma perché avrebbe mostrato un isomorfismo tra i due problemi: avrebbe cioè mostrato come si può associare a ciascun sottoinsieme dei numeri da 1 a n una stringa binaria di n numeri. Avete capito come? E ve ne sareste accorti se non ve l’avessi segnalato?