[Zadatak]: Polinomi, teorija brojeva, kombinatorika, pa sve to odjedared

[Zadatak]: Polinomi, teorija brojeva, kombinatorika, pa sve to odjedared 08.07.2005. u 10:02 · pre 259 meseci #1

Naći broj polinoma čiji koeficijenti pripadaju skupu $\{0,1,2,3\}$ takvih da je $P(2)=n$ (naravno, traži se funkcija od $n$ ).

Ovaj zadatak ima zanimljivu pričicu. Moj profesor ga je našao u nekoj rumunskoj knjižici ali pošto mu se nije svidelo njihovo rešenje on ga je rešio na svoj način (meni se inače čini da je njihovo rešenje lepše od njegovog ali svako ima svoj ukus). Onda je postavio meni zadatak da bi video da li ću ga i kako ja rešiti, i posle nekih 5 minuta sam našao tako divno rešenje (koje se mnogo razlikuje i od njegovog i od zvaničnog, i dosta je kraće) da on nije mogao da veruje. Ako neko reši dobije od mene za nagradu sva tri rešenja koja ja znam (od kojih ovo poslednje, ne zato što je moje, ali je stvarno fenomenalno) :)

_{[Ovu poruku je menjao Bojan Basic dana 08.07.2005. u 11:04 GMT+1]}

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Polinomi, teorija brojeva, kombinatorika, pa sve to odjedared 09.07.2005. u 01:13 · pre 259 meseci #2

Zadatak se svodi na pronalaženje broja zapisa broja $n$ u osnovi 2 ali sa dopuštenjem da cifre budu od 0 do 3.
Ako prvo pođemo od regularnog zapisa u osnovi 2, dakle samo preko 0 i 1, onda premeštanjem jedinica "udesno" one uvećavaju cifru desno od sebe za 2.Uzastopnim prebacivanjem po jedne cifre (ili njenog dela), pazeći pri tom da ne premašimo gornju granicu za cifre, možemo dobiti sve one neobične zapise.
Da bi bilo jasnije na šta mislim, evo nekih primera:

5= 101= 021= 013
6= 110= 030= 102= 022
7= 111= 031= 103= 023

12= 1100=0300=1020=0220=1012=0212=0132
13= 1101=0301=1021=0221=1013=0213=0133

Dakle, ako sa $a_n$ označimo broj zapisa broja $n$ , onda je jasno da mora važiti $a_{2n+1}=a_{2n}$ , jer se iz svakog zapisa za $2n$ , uvećanjem poslednje cifre za 1, dobija zapis za $2n+1$ , ( jasno je da su poslednje cifre u bilo kom zapisu za $2n$ ili 0 ili 2, pa njihovo uvećanje za jedan daje korektnu cifru) i obrnuto, na ekvivalentan način dobijamo da svaki zapis za $2n+1$ proizvodi jedan zapis za $2n$ .

Dakle, dovoljno je pronaći $a_{2n}$ .
Ako pođemo od regularnog binarnog zapisa vidimo da je zapis broja $n$ početni deo zapisa broja $2n$ .
Pošto je $2n$ paran, to je poslednja cifra 0, a početni deo je zapis broja $n$ . Dakle, zapisa broja $2n$ , koji se završavaju sa 0, ima tačno onoliko koliko i zapisa broja $n$ , pa ako je $n>0$ onda je u nekom od zapisa broja $n$ poslednja cifra barem 1, pa postoje i zapisi broja $2n$ koji se završavaju sa 2, jer možemo prebaciti jednu jedinicu iz poslednje cifre zapisa broja $n$ , sada broj $n$ postaje broj $n-1$ a njegovih zapisa ima $a_{n-1}$ , pa smo došli do formule:

$a_{2n}=a_n+a_{n-1}$ .
Jasno je da važi $a_0=a_1=1$ .

Lako je proveriti da je $a_n=\left\lfloor\frac{n}{2}\right\rfloor+1$

Nadam se da je ovo dovoljno za nagradu

_{[Ovu poruku je menjao uranium dana 09.07.2005. u 02:15 GMT+1]}

_{[Ovu poruku je menjao uranium dana 09.07.2005. u 02:43 GMT+1]}

_{[Ovu poruku je menjao uranium dana 09.07.2005. u 02:56 GMT+1]}

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak]: Polinomi, teorija brojeva, kombinatorika, pa sve to odjedared 09.07.2005. u 02:17 · pre 259 meseci #3

Uh bre, iskomplikovao si ga samo tako, ali bitno je da je tačno. Zaslužio si svoju nagradu :)

Rešenje 1: (zvanično rešenje)

Neka je $P(x)$ jedan polinom koji zadovoljava uslove zadatka (za neko odabrano $n$ ). Definišimo funkciju koja preslikava $P(x)$ na $Q(x)$ tako da su koeficijenti polinom $Q(x)$ ostaci koeficijenata polinoma $P(x)$ pri deljenju sa $2$ . Posmatrajmo šta se dešava pri ovakvom preslikavanju: svaki koeficijent polinoma $P(x)$ ili umanjujemo za $2$ ili ostavljamo isti, na osnovu čega sledi da se vrednost $P(2)$ (što je jednako $n$ ) može smanjiti za broj oblika $2S$ gde je $S$ zbir nekoliko stepena dvojke (i to tačno onih stepena čije koeficijente smo smanjivali). Pošto se svaki prirodan broj može jednoznačno predstaviti kao zbir stepena dvojki (to je ekvivalentno njegovom binarnom zapisu) sledi da je posmatrana funkcija zapravo bijekcija. Moguće vrednosti polinoma $Q(2)$ su $\{n,n-2,n-4,n-6\dots\}$ (pozitivni brojevi) kojih očigledno ima $\left\lfloor\frac n 2\right\rfloor+1$ pa toliko ima i polinoma $P(x)$ .

Rešenje 2: (profesorovo rešenje)

Neka je $a_0+2a_1+\cdots+2^ma_m=n$ . Primetimo da su $\frac{n-a_0}2=a_1+2a_2+\cdots+2^{m-1}a_m$ zapravo svi mogući zapisi broja $\frac{n-a_0}2$ . Za neparno $n$ broj $a_0$ očigledno iznosi $1$ ili $3$ , a za parno je $a_0$ jednako $0$ ili $2$ , pa možemo sastaviti sledeću rekurentnu relaciju:

$f(n)=\left\{\begin{array}{ll} f\left(\frac{n-1}2\right)+f\left(\frac{n-3}2\right),&\quad n\equiv 1\pmod 2\\ f\left(\frac n 2\right)+f\left(\frac{n-2}2\right),&\quad\hbox{ina\v ce}\end{array}\right.$

Isprobavanjem za male vrednosti $n$ možemo pretpostaviti da je rešenje $\left\lfloor\frac n 2\right\rfloor+1$ , za koje dokazujemo indukcijom da važi napisana rekurentna formula (taj deo preskačem ovde pošto nije težak a nema mnogo veze sa samim zadatkom, sve je dalje stvar tehnike).

Rešenje 3: (moje rešenje)

Neka je $a_0+2a_1+\cdots+2^ma_m=n$ . To možemo zapisati i kao $n=(a_0+4a_2+16a_3+\cdots)+2\cdot(a_1+4a_3+16a_5+\cdots)$ . Pošto koeficijenti pripadaju skupu $\{0,1,2,3\}$ ovo u zagradama možemo posmatrati kao prirodne brojeve zapisane u osnovi $4$ , pa je broj načina da se $n$ predstavi u traženom obliku jednak broju celih nenegativnih rešenja jednačine $n=x+2y$ , odnosno traženi broj je $\left\lfloor\frac n 2\right\rfloor+1$ .

Eto, jesi li zadovoljan nagradom? :)

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Polinomi, teorija brojeva, kombinatorika, pa sve to odjedared 09.07.2005. u 13:38 · pre 259 meseci #4

Jesam

Moje rešenje je najbliže rešenju pod 2.
A ono treće je stvarno prelepo

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak]: Polinomi, teorija brojeva, kombinatorika, pa sve to odjedared 12.07.2005. u 12:23 · pre 259 meseci #5

Vidim naucio si funkcije generatrisa :-)

Potpis

Math is like love. A simple idea but it can get complicated.

Re: [Zadatak]: Polinomi, teorija brojeva, kombinatorika, pa sve to odjedared 21.07.2005. u 16:32 · pre 258 meseci #6

@cassey:
To mi je bio maturski (ako hoćeš mogu ti poslati) :)

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Srodne teme