Zadatak se svodi na pronalaženje broja zapisa broja
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
označimo broj zapisa broja
, onda je jasno da mora važiti
, jer se iz svakog zapisa za
, uvećanjem poslednje cifre za 1, dobija zapis za
, ( jasno je da su poslednje cifre u bilo kom zapisu za
ili 0 ili 2, pa njihovo uvećanje za jedan daje korektnu cifru) i obrnuto, na ekvivalentan način dobijamo da svaki zapis za
proizvodi jedan zapis za
.
Dakle, dovoljno je pronaći
.
Ako pođemo od regularnog binarnog zapisa vidimo da je zapis broja
početni deo zapisa broja
.
Pošto je
paran, to je poslednja cifra 0, a početni deo je zapis broja
. Dakle, zapisa broja
, koji se završavaju sa 0, ima tačno onoliko koliko i zapisa broja
, pa ako je
onda je u nekom od zapisa broja
poslednja cifra barem 1, pa postoje i zapisi broja
koji se završavaju sa 2, jer možemo prebaciti jednu jedinicu iz poslednje cifre zapisa broja
, sada broj
postaje broj
a njegovih zapisa ima
, pa smo došli do formule:
.
Jasno je da važi
.
Lako je proveriti da je
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]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.