• lunedì 8 luglio 2013

Basta saperlo…

Spesso in matematica sapere qual è il risultato da dimostrare fa anche intuire qual è la strada da prendere per dimostrarlo. Il guaio è appunto riuscire a 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.

(altro…)

Continua sul Post