| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
davor
Gost
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
 Postano: 1:13 uto, 21. 1. 2003 Naslov: Re: zadaci |
    |
|
|
[quote="davor"]2) Odredi broj binarnih brojeva od n znamenaka koji imaju tocno jedan par susjednih nula.[/quote]
Za prvi cu jos malo razmisliti, a drugi ide ovako. Kao prvo, pretpostavljam da se radi o binarnim nizovima duljine n. Razlika je u tome sto n-znamenkasti binarni broj mora poceti jedinicom. Ali broj nizova duljine n-1 jednak je broju n-znamenkastih bin. brojeva (bijekcija je nadodavanje/ulkanjanje vodece jedinice), pa i nije tako vazno.
Glavna ideja je da dvije susjedne jedinice "slijepimo" i tako dobijemo niz duljine n-1 bez susjednih nula. Recimo da u tom nizu ima k nula i n-1-k jedinica. Onda bi njihov broj bio {n-k \choose k}; prvo stavimo jedinice, pa biramo mjesta izmedju jedinica (ukljucujuci lijevo i desno) na koja cemo staviti nule. Na kraju "podebljamo" slijepljeni par nula, sto mozemo na k nacina.
Konacno rjesenje je \sum_{k\ge 1} k {n-k \choose k}. Koga veseli neka pokusa izracunati ovu sumu, ali nisam siguran moze li se dobiti zatvoreni oblik bez specijalnih funkcija.
| davor (napisa): | | 2) Odredi broj binarnih brojeva od n znamenaka koji imaju tocno jedan par susjednih nula. |
Za prvi cu jos malo razmisliti, a drugi ide ovako. Kao prvo, pretpostavljam da se radi o binarnim nizovima duljine n. Razlika je u tome sto n-znamenkasti binarni broj mora poceti jedinicom. Ali broj nizova duljine n-1 jednak je broju n-znamenkastih bin. brojeva (bijekcija je nadodavanje/ulkanjanje vodece jedinice), pa i nije tako vazno.
Glavna ideja je da dvije susjedne jedinice "slijepimo" i tako dobijemo niz duljine n-1 bez susjednih nula. Recimo da u tom nizu ima k nula i n-1-k jedinica. Onda bi njihov broj bio {n-k \choose k}; prvo stavimo jedinice, pa biramo mjesta izmedju jedinica (ukljucujuci lijevo i desno) na koja cemo staviti nule. Na kraju "podebljamo" slijepljeni par nula, sto mozemo na k nacina.
Konacno rjesenje je \sum_{k\ge 1} k {n-k \choose k}. Koga veseli neka pokusa izracunati ovu sumu, ali nisam siguran moze li se dobiti zatvoreni oblik bez specijalnih funkcija.
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: 
Lokacija: /sbin/init
|
|
| [Vrh] |
|
vjekovac
Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: 
|
| Postano: 20:47 čet, 23. 1. 2003 Naslov: |
|
|
|
[quote]1) Neka je S n-teroclani skup cijelih brojeva. Da li je uvijek moguce odabrati neki njegov podskup takav da je suma brojeva u tom podskupu djeljiva s n?
[/quote]
Da, moguce je. Evo kratkog dokaza.
Oznacimo elemente od S sa: a_1, a_2, ..., a_n te stavimo:
S_0 := 0
S_1 := a_1
S_2 := a_1 + a_2
...
S_n := a_1 + a_2 +...+ a_n
Po Dirichletovom principu, medju brojevima S_0 ,..., S_n neka dva daju isti ostatak pri dijeljenju s n.
To znaci da postoje 0<=p<q<=n takvi da je
S_q - S_p = a_(p+1) +...+ a_q djeljivo s n.
I to je to... 8)
Ima jedan slican (iako dosta tezi) zadatak koji su (jos dosta davno) postavili i rijesili Erdos, Ginsburg i Ziv:
Dokazati da (2n-1)-clani skup cijelih brojeva ima (bar jedan) n-clani podskup kojem je suma elemenata djeljiva s n.
Ako nekog veseli, nek' se zabavlja :wink: , ali problem nije bas bezazlen kako se cini. (Ipak, ima prilicno elegantno rjesenje.)
| Citat: | 1) Neka je S n-teroclani skup cijelih brojeva. Da li je uvijek moguce odabrati neki njegov podskup takav da je suma brojeva u tom podskupu djeljiva s n?
|
Da, moguce je. Evo kratkog dokaza.
Oznacimo elemente od S sa: a_1, a_2, ..., a_n te stavimo:
S_0 := 0
S_1 := a_1
S_2 := a_1 + a_2
...
S_n := a_1 + a_2 +...+ a_n
Po Dirichletovom principu, medju brojevima S_0 ,..., S_n neka dva daju isti ostatak pri dijeljenju s n.
To znaci da postoje 0⇐p<q⇐n takvi da je
S_q - S_p = a_(p+1) +...+ a_q djeljivo s n.
I to je to... 
Ima jedan slican (iako dosta tezi) zadatak koji su (jos dosta davno) postavili i rijesili Erdos, Ginsburg i Ziv:
Dokazati da (2n-1)-clani skup cijelih brojeva ima (bar jedan) n-clani podskup kojem je suma elemenata djeljiva s n.
Ako nekog veseli, nek' se zabavlja  , ali problem nije bas bezazlen kako se cini. (Ipak, ima prilicno elegantno rjesenje.)
|
|
| [Vrh] |
|
|
