i)Calcolare $ \displaystyle U_7 $.
ii)Calcolare il minimo n tale che $ U_n \ge 2006 $.
buoni conti..
nazionali romania 2006
nazionali romania 2006
definiamo "collegato" un insieme di naturali in cui esiste almeno un x per cui è presente anche (x-1) o (x+1). Chiamiamo $ U_n $ il numero di sottoinsiemi collegati nell'insieme {1, 2, 3...n}.
i)Calcolare $ \displaystyle U_7 $.
ii)Calcolare il minimo n tale che $ U_n \ge 2006 $.
buoni conti..
i)Calcolare $ \displaystyle U_7 $.
ii)Calcolare il minimo n tale che $ U_n \ge 2006 $.
buoni conti..
The only goal of science is the honor of the human spirit.
-
matemark90
- Messaggi: 67
- Iscritto il: 03 nov 2006, 20:02
- Località: la città del carnevale (RE)
Ci provo:
i) ho diviso per casi in base al numero di elementi dei sottoinsiemi che voglio contare:
con 7,6,5 elementi i possibili sottoinsiemi vanno bene tutti quindi abbiamo $ \displaystyle{\binom{7}{7} + \binom{7}{6} + \binom{7}{5}} $
con 4 elementi vanno bene tutti tranne {1,3,5,7} quindi $ \displaystyle{\binom{7}{4} - 1 } $
con 3 elementi ho suddiviso ancora e ho contato quelli che non soddisfano: quelli che iniziano con 1,3 sono 3, con 1,4 sono 2, con 1,5 è solo 1; con 2,4 sono 2, con 2,5 è 1; con 3,5 è 1. Quindi $ \displaystyle{\binom{7}{3} - 10} $
con 2 elementi quelle che soddisfano sono le coppie di consecutivi che sono 6
e ovviamente non è possibile avere insiemi con 1 elemento.
Quindi dovrebbe risultare 1+7+21+34+25+6+1=95
ii) ho visto che dato un certo $ U_n $ con n dispari abbiamo come sopra per pigeonhole che si hanno $ \displaystyle{\binom{n}{n} + \binom{n}{n-1} + ... + } $ (qui non sapevo come scrivere n su la parte intera di n mezzi arrotondata per ecceso) $ -1 $ che è uguale a $ \frac{2^n}{2}-1 $. Gli insiemi non considerati sono sicuramente minori di un numero sufficientemente grande per dire che 11<n<=13. Non è difficile escludere 2048-2006=42 casi. Basta considerare gli insiemi di 2 elementi.
per n pari abbiamo $ \frac{2^n}{2}-2 $ per gli insiemi composti da n/2,n/2+1,...,n elementi che per n=12 vale 2046.
Scusate la confusione che ho fatto nel (ii). Eventualmente chiarirò certe affermazioni espresse un po' male.
ps: non sono per niente sicuro che sia esatta
i) ho diviso per casi in base al numero di elementi dei sottoinsiemi che voglio contare:
con 7,6,5 elementi i possibili sottoinsiemi vanno bene tutti quindi abbiamo $ \displaystyle{\binom{7}{7} + \binom{7}{6} + \binom{7}{5}} $
con 4 elementi vanno bene tutti tranne {1,3,5,7} quindi $ \displaystyle{\binom{7}{4} - 1 } $
con 3 elementi ho suddiviso ancora e ho contato quelli che non soddisfano: quelli che iniziano con 1,3 sono 3, con 1,4 sono 2, con 1,5 è solo 1; con 2,4 sono 2, con 2,5 è 1; con 3,5 è 1. Quindi $ \displaystyle{\binom{7}{3} - 10} $
con 2 elementi quelle che soddisfano sono le coppie di consecutivi che sono 6
e ovviamente non è possibile avere insiemi con 1 elemento.
Quindi dovrebbe risultare 1+7+21+34+25+6+1=95
ii) ho visto che dato un certo $ U_n $ con n dispari abbiamo come sopra per pigeonhole che si hanno $ \displaystyle{\binom{n}{n} + \binom{n}{n-1} + ... + } $ (qui non sapevo come scrivere n su la parte intera di n mezzi arrotondata per ecceso) $ -1 $ che è uguale a $ \frac{2^n}{2}-1 $. Gli insiemi non considerati sono sicuramente minori di un numero sufficientemente grande per dire che 11<n<=13. Non è difficile escludere 2048-2006=42 casi. Basta considerare gli insiemi di 2 elementi.
per n pari abbiamo $ \frac{2^n}{2}-2 $ per gli insiemi composti da n/2,n/2+1,...,n elementi che per n=12 vale 2046.
Scusate la confusione che ho fatto nel (ii). Eventualmente chiarirò certe affermazioni espresse un po' male.
ps: non sono per niente sicuro che sia esatta
Hasta la Carla... SIEMPRE!!!
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
-
matemark90
- Messaggi: 67
- Iscritto il: 03 nov 2006, 20:02
- Località: la città del carnevale (RE)
1) Perchè ho dormito: ho considerato 2 volte il primo caso mentre trascrivevo le risposte 
2) (x-1) o (x+1) significa esattamente uno tra i due? Io l'ho interpretato corretto perchè comunque uno dei due esiste.
2) (x-1) o (x+1) significa esattamente uno tra i due? Io l'ho interpretato corretto perchè comunque uno dei due esiste.
Hasta la Carla... SIEMPRE!!!
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.