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 – Bn di lunghezza n che non contengano all’interno due cifre 1 consecutive? Per esempio, 000101 è valida, mentre 001101 no.
- Quanti sono i sottoinsiemi Sn 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 Bn è 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.
