OliForum Matematico

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..

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

question1: perchè al conto finale di i) aggiungi 1 come ultimo addendo?
question2:e.g.{1,2,5,6,7}appartiene a $ U_7 $??

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.

mm, scuse me per la 2,comunque anch'io feci come te..nonè una certezza, ma come dice maxibon "two is mej che one"