nazionali romania 2006

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

nazionali romania 2006

Messaggio da jordan » 09 gen 2008, 00:48

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.. :)
The only goal of science is the honor of the human spirit.

Avatar utente
matemark90
Messaggi: 67
Iscritto il: 03 nov 2006, 20:02
Località: la città del carnevale (RE)

Messaggio da matemark90 » 12 gen 2008, 19:23

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
Hasta la Carla... SIEMPRE!!!
Per tre cose vale la pena di vivere: la matematica, la musica e l'amore.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 12 gen 2008, 21:43

question1: perchè al conto finale di i) aggiungi 1 come ultimo addendo?
question2:e.g.{1,2,5,6,7}appartiene a $ U_7 $??
The only goal of science is the honor of the human spirit.

Avatar utente
matemark90
Messaggi: 67
Iscritto il: 03 nov 2006, 20:02
Località: la città del carnevale (RE)

Messaggio da matemark90 » 13 gen 2008, 01:43

1) Perchè ho dormito: ho considerato 2 volte il primo caso mentre trascrivevo le risposte :oops:
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.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 13 gen 2008, 04:07

mm, scuse me per la 2,comunque anch'io feci come te..nonè una certezza, ma come dice maxibon "two is mej che one"
The only goal of science is the honor of the human spirit.

Rispondi