Pagina 1 di 1
Sottoinsiemi porosi
Inviato: 09 mag 2007, 14:53
da salva90
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
Inviato: 09 mag 2007, 15:56
da fede90
mmh...mirabilandia 2007! penso ke questo esercizio abbia dato del filo da torcere a piu di qualcuno...
Inviato: 09 mag 2007, 16:00
da salva90
fede90 ha scritto:mmh...mirabilandia 2007! penso ke questo esercizio abbia dato del filo da torcere a piu di qualcuno...
già, qualcuno ha avuto la pessima idea di contarli brutalmente (chi ha detto salva90?
)
e meno male che giove ci ha sbagliato il calcolo e io no
Inviato: 09 mag 2007, 20:49
da moebius
Possibile che siano 769?
Inviato: 09 mag 2007, 21:12
da Pigkappa
No
Inviato: 09 mag 2007, 21:13
da salva90
moebius ha scritto:Possibile che siano 769?
no, affatto
Inviato: 09 mag 2007, 21:22
da moebius
No, l'avevo fatta troppo semplice... mi sa che non meno!
Inviato: 09 mag 2007, 21:59
da fede90
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!
Inviato: 09 mag 2007, 22:06
da salva90
fede90 ha scritto:ma ci si impiegano delle ore a contarli tutti!
no, mi è bastato 50 imnuti circa, più 30 ricontrolli vari
e comunque la sol ufficiale è semplice, avuta l'idea
Inviato: 10 mag 2007, 01:52
da MindFlyer
504?
Viene una ricorsione carina. Non so come sia la soluzione ufficiale, ma se ci si accontenta di calcolarlo su 10 elementi, basta vedere la ricorsione per ridurre il tutto a poche somme.
Inviato: 10 mag 2007, 08:21
da salva90
Si Mind, l'idea era quella.
Se magari mi veniva in mente in gara risparmiavo un bel pò di conticini
Inviato: 10 mag 2007, 12:50
da MindFlyer
Quando ci sono cose del genere, la ricorsione è la prima cosa che provo. Perché farsi venire idee quando i problemi si risolvono da sé?