Calcolare il numero di sottoinsiemi porosi dell'insieme $ \{1, 2, 3..., 10\} $
Good luck
Sottoinsiemi porosi
Sottoinsiemi porosi
Diciamo che un sottoinsieme di un dato insieme è poroso se è vuoto o se non contiene tre numeri consecutivi.
Calcolare il numero di sottoinsiemi porosi dell'insieme $ \{1, 2, 3..., 10\} $
Good luck
Calcolare il numero di sottoinsiemi porosi dell'insieme $ \{1, 2, 3..., 10\} $
Good luck
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
già, qualcuno ha avuto la pessima idea di contarli brutalmente (chi ha detto salva90?fede90 ha scritto:mmh...mirabilandia 2007! penso ke questo esercizio abbia dato del filo da torcere a piu di qualcuno...
)e meno male che giove ci ha sbagliato il calcolo e io no
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
ma ci si impiegano delle ore a contarli tutti!
io ho cominciato a fare delle semplici osservazioni...
chiamando con $ $P_n$ $ il numero dei sottoinsiemi porosi di $ $n$ $ elementi, è facile vedere che $ $P_0=1$ $ e $ $P_1=10$ $ mentre $ $P_2=$ $ $ $10\choose 2$ $, perchè nessuno degli insiemi di due elementi può avere tre elementi consecutivi.
Inoltre anche $ $P_{10}=0$ $ $ $P_9=0$ $ e $ $P_8=0$ $.
Per $ $P_3$ $ bisogna togliere a $ $10\choose 3$ $ gli $ $8$ $ insiemi di 3 elementi consecutivi.
Per gli altri avevo fatto un ragionamento un po' contorto, avvicinandomi comunque abbastanza al risultato (mi veniva sui 540)...
la soluzione ufficiale non l'ho letta perbene ma mi e sembrata abbastanza semplice e carina!
io ho cominciato a fare delle semplici osservazioni...
chiamando con $ $P_n$ $ il numero dei sottoinsiemi porosi di $ $n$ $ elementi, è facile vedere che $ $P_0=1$ $ e $ $P_1=10$ $ mentre $ $P_2=$ $ $ $10\choose 2$ $, perchè nessuno degli insiemi di due elementi può avere tre elementi consecutivi.
Inoltre anche $ $P_{10}=0$ $ $ $P_9=0$ $ e $ $P_8=0$ $.
Per $ $P_3$ $ bisogna togliere a $ $10\choose 3$ $ gli $ $8$ $ insiemi di 3 elementi consecutivi.
Per gli altri avevo fatto un ragionamento un po' contorto, avvicinandomi comunque abbastanza al risultato (mi veniva sui 540)...
la soluzione ufficiale non l'ho letta perbene ma mi e sembrata abbastanza semplice e carina!
-
MindFlyer
-
MindFlyer