Catatan si Jay

November 9, 2010

Menghitung Kemunculan Karakter ‘1’ Pada Bilangan n-Digit

Filed under: Matematika, Peluang, Puzzle — Hendra Jaya @ 1:12 pm

Problem

  • Kemunculan karakter ‘1’ pada angka 10 adalah 1
  • Kemunculan karakter ‘1’ pada angka 51 adalah 1
  • Kemunculan karakter ‘1’ pada angka 11 adalah 2
  • Kemunculan karakter ‘1’ pada angka 121 adalah 2
  • Kemunculan karakter ‘1’ pada angka 1141 adalah 3
  • dst…

Pertanyaannya :

  • Diketahui A=\{1,2,3,\ldots,999,1000\}.
    • Berapa banyak bilangan di dalam himpunan tersebut yang mengandung karakter ‘1’?
    • Berapa kali karakter ‘1’ muncul di dalam himpunan A?
  • Misalkan N=\{n_1,n_2,n_3,\ldots,n_k\} adalah himpunan seluruh bilangan n-digit.
    • Berapa banyak bilangan di dalam himpunan N yang mengandung karakter 1?
    • Berapa kali karakter ‘1’ muncul pada himpunan tersebut?

Sumber : Nanda Daiva Putra

Referensi : 10th Binomial Transform dan Number of “9ish numbers” with n digits

Dear Diary

Pra-Pembahasan 1 (Leading Zero)

Normalnya, awalan 0 (leading zero) tidak diperbolehkan dalam menulis angka. Sebagai contoh :

  • Penulisan 06 dianggap tidak valid, yang valid adalah 6
  • Penulisan 029 dianggap tidak valid, yang valid adalah 29

Sehingga :

Banyaknya bilangan 1 digit yang dapat dibentuk adalah 9
Banyaknya bilangan 2 digit yang dapat dibentuk adalah 9 . 10 = 90
Banyaknya bilangan 3 digit yang dapat dibentuk adalah 9 . 10 . 10 = 900
dst..

Namun, seandainya leading zero diperbolehkan, yaitu setiap karakter pada himpunan C=\{0,1,2,3,4,5,6,7,8,9\} boleh dipakai, maka :

Banyaknya bilangan 1 digit yang dapat dibentuk adalah 10
Banyaknya bilangan 2 digit yang dapat dibentuk adalah 10 . 10 = 100
Banyaknya bilangan 3 digit yang dapat dibentuk adalah 10 . 10 . 10 = 1000
dst…

Dari sini kita dapat menyimpulkan bahwa :

  1. Banyaknya bilangan n-digit yang dapat dibentuk jika awalan 0 tidak diperbolehkan (non-leading zero) adalah 9.10^{n-1}
  2. Banyaknya bilangan n-digit yang dapat dibentuk jika awalan 0 (leading zero) diperbolehkan adalah 10^{n}

Pra-Pembahasan 2 (Kemunculan Karakter ‘1’ pada Leading Zero)

Jika awalan 0 (non-leading zero) tidak diperbolehkan, maka :

Bilangan-bilangan 1 digit yang mengandung karakter ‘1’ adalah \{1\}
Banyaknya bilangan 1 digit yang mengandung karakter ‘1’ adalah 1 buah.
Total kemunculan karakter ‘1’ pada bilangan 1 digit adalah 1 kali.

Bilangan-bilangan 2 digit yang mengandung karakter ‘1’ adalah \{10,11,12,13,14,15,16,17,18,19,21,31,41,51,61,71,81,91\}
Banyaknya bilangan 2 digit yang mengandung karakter ‘1’ adalah 18 buah.
Total kemunculan karakter ‘1’ pada bilangan 2 digit adalah 19 kali.

Jika awalan 0 (leading zero) diperbolehkan, maka :

Bilangan-bilangan 1 digit yang mengandung karakter ‘1’ adalah \{1\}
Banyaknya bilangan 1 digit yang mengandung karakter ‘1’ adalah 1 buah.
Total kemunculan karakter ‘1’ pada bilangan 1 digit adalah 1 kali.

Bilangan-bilangan 2 digit yang mengandung karakter ‘1’ adalah \{01,10,11,12,13,14,15,16,17,18,19,21,31,41,51,61,71,81,91\}
Banyaknya bilangan 2 digit yang mengandung karakter ‘1’ adalah 19 buah.
Total kemunculan karakter ‘1’ pada bilangan 2 digit adalah 20 kali.

Mengapa terdapat perbedaan antara kasus leading zero dan kasus non-leading zero?

Jawabannya terletak pada leading zero itu sendiri.

Pada kasus non-leading zero, bilangan 1 tidak akan muncul pada bilangan 2-digit karena bilangan 1 hanya terdiri dari 1 buah digit. Selamanya begitu. Tidak bisa “naik pangkat” menjadi bilangan 2-digit.

Sebaliknya, pada kasus leading zero, bilangan 1 akan muncul pada bilangan 2-digit. Yaitu dengan memberikan awalan 0 (leading zero) pada bilangan 1, maka akan dihasilkan bilangan baru 01 yang panjangnya 2 digit. Kita katakan “1 naik pangkat menjadi bilangan 2-digit”.

Dari logika ini, semua bilangan 1-digit akan naik pangkat menjadi bilangan 2-digit, lalu naik pangkat menjadi bilangan 3-digit, dan seterusnya sampai menjadi bilangan n-digit.
Dari logika yang sama, semua bilangan 2-digit akan naik pangkat menjadi bilangan 3-digit, lalu naik pangkat menjadi bilangan 4-digit, dan seterusnya sampai menjadi bilangan n-digit.
dst..
Begitu pula dengan bilangan (n-1)-digit. Bilangan ini akan naik pangkat menjadi bilangan n-digit.

Lantas, apa hubungan antara bilangan non-leading zero dan leading zero?

Misalkan :

  • f(n) adalah fungsi yang menghitung banyaknya kemunculan ‘1’ pada seluruh bilangan n-digit non-leading zero.
  • g(n) adalah fungsi yang menghitung banyaknya kemunculan ‘1’ pada seluruh bilangan n-digit leading zero.

Secara intuitif kita tahu bahwa g(n) pasti lebih besar dari f(n). Hal ini cukup jelas juga secara matematis, mengingat bilangan-bilangan yang leading zero boleh menggunakan 0, sementara bilangan-bilangan yang non-leading zero tidak.

Cukup jelas juga bahwa selisih antara g(n) dan f(n) berasal dari bilangan-bilangan yang “naik pangkat”.

Lantas, berapa banyak bilangan-bilangan yang “naik pangkat”?

Semua bilangan-bilangan berdigit lebih kecil dari n akan naik pangkat. Mulai dari berdigit 1 sampai berdigit n-1.

Banyaknya bilangan berdigit 1 yang naik pangkat adalah f(1)
Banyaknya bilangan berdigit 2 yang naik pangkat adalah f(2)
Banyaknya bilangan berdigit 3 yang naik pangkat adalah f(3)
dst…
Banyaknya bilangan berdigit n-1 yang naik pangkat adalah f(n-1)

Sehingga, total bilangan yang naik pangkat adalah f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)

Jika dikembalikan ke relasi antara g(n) dan f(n), maka akan kita peroleh :

\begin{array}{rcl}g(n)-f(n)&=&f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)\\g(n)&=&f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)+f(n)\end{array}

Pra-Pembahasan 3 (Sebaran Bilangan yang Mengandung karakter ‘1’ Pada Bilangan n-digit Leading Zero)

Misalkan pada seluruh bilangan n-digit leading zero, terdapat :

  • x buah bilangan yang mengandung karakter ‘1’
  • y buah bilangan yang tidak mengandung karakter ‘1’
  • g(n)=z buah kemunculan karakter ‘1’.

Jelas sekali bahwa relasi antara x dan y adalah x+y=10^n

Selanjutnya, kita asumsikan :

  • Ada a_1 buah bilangan yang mengandung 1 buah karakter ‘1’
  • Ada a_2 buah bilangan yang mengandung 2 buah karakter ‘1’
  • Ada a_3 buah bilangan yang mengandung 3 buah karakter ‘1’
  • dst…
  • Ada a_{n-1} buah bilangan yang mengandung n-1 buah karakter ‘1’
  • Ada a_n buah bilangan yang mengandung n buah karakter ‘1’

Banyaknya bilangan yang mengandung karakter ‘1’ adalah a_1+a_2+a_3+\ldots+a_{n-1}+a_n alias x.
Sehingga kita peroleh invarian x=a_1+a_2+a_3+\ldots+a_{n-1}+a_n

Sebaliknya, banyaknya kemunculan karakter ‘1’ adalah 1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n alias z.
Sehingga kita peroleh invarian lainnya, yakni g(n)=z=1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n

Bagaimana dengan y, adakah cara untuk menghitungnya?

Untuk mencari nilai y tidak terlalu sulit. Cukup menggunakan “pohon kemungkinan”.

Karena terdiri dari n-digit dan leading zero, maka setiap digit-nya boleh menggunakan bilangan-bilangan pada himpunan \{0,2,3,4,5,6,7,8,9\} yang banyaknya (kardinalitas) ada 9 buah. Sehingga :

y=9.9.9\ldots 9.9=9^n

Knuth Mistakes

Pembahasan

Misalkan \overline{ABCDE\ldots} adalah sebuah bilangan n digit.

Bilangan ini dapat kita pecah menjadi 2 bagian yaitu \overline{A} dan \overline{BCDE\ldots} dimana :

  • \overline{A} jelas merupakan bilangan 1 digit dan tidak boleh dimulai dengan 0 (non-leading zero).
    Sehingga himpunan bilangan yang mungkin untuk \overline{A} adalah \{1,2,3,4,5,6,7,8,9\}.
  • Sedikit berbeda, \overline{BCDE\ldots} merupakan bilangan (n-1)-digit yang boleh dimulai dari 0.
    Sehingga himpunan bilangan yang mungkin untuk \overline{B},\overline{C},\overline{D},\overline{E},\ldots adalah \{0,1,2,3,4,5,6,7,8,9\}.

Secara intuitif, kita dapat menyadari bahwa munculnya karakter ‘1’ hanya mungkin terjadi dalam 3 buah kasus, yaitu :

  1. Karakter ‘1’ hanya disumbangkan oleh \overline{A}
  2. Karakter ‘1’ hanya disumbangkan oleh \overline{BCDE\ldots}
  3. Karakter ‘1’ disumbangkan oleh kedua pihak, yaitu \overline{A} dan \overline{BCDE\ldots}

Kasus 1

Karena karakter ‘1’ hanya disumbangkan oleh \overline{A}, berarti :

  • Hanya ada 1 buah nilai yang mungkin untuk \overline{A}
  • Ada y buah nilai yang mungkin untuk \overline{BCDE\ldots}

Sehingga :

  • Banyaknya bilangan yang mengandung ‘1’ pada kasus 1 adalah 1.y=y
  • Banyaknya kemunculan karakter ‘1’ ada sebanyak y kali

Catatan : Walaupun \overline{BCDE\ldots} tidak memiliki satupun karakter ‘1’, namun \overline{BCDE\ldots} berjumlah y buah. Ketika dipasangkan dengan \overline{A} maka akan muncul y buah karakter ‘1’ yang baru.

Kasus 2

Dalam kasus ini, karakter ‘1’ hanya disumbangkan oleh \overline{BCDE\ldots}, yang berarti :

  • Ada 8 buah nilai yang mungkin untuk \overline{A}, yaitu \{2,3,4,5,6,7,8,9\}
  • Ada x buah nilai yang mungkin untuk \overline{BCDE\ldots}
  • Ada z buah kemunculan karakter ‘1’ pada \overline{BCDE\ldots}

Sehingga :

  • Banyaknya bilangan yang mengandung ‘1’ pada kasus 2 adalah 8.x=8x
  • Banyaknya kemunculan karakter ‘1’ ada sebanyak 8.z=8z kali

Kasus 3

Kasus ini adalah kasus yang paling tricky. Perhatikan bahwa :

  • Ada 1 buah nilai yang mungkin untuk \overline{A}
  • Ada x buah nilai yang mungkin untuk \overline{BCDE\ldots}
  • Ada z buah kemunculan karakter ‘1’ pada \overline{BCDE\ldots}

Sebaran dari z adalah 1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n
Ketika digabungkan dengan \overline{A}, sebarannya akan naik menjadi 2.a_1+3.a_2+4.a_3+\ldots+n.a_{n-1}+(n+1).a_n.

Catatan : Kenaikan sebaran terjadi karena terjadi penggabungan (concatenation) dengan karakter ‘1’ yang berasal dari \overline{A}.  Sebagai contoh, bilangan 31216 semula memiliki 2 buah karakter ‘1’. Ketika dibubuhi prefix ‘1’ akan menjadi 131216 yang mengandung 3 buah karakter ‘1’.

Jika disederhanakan, bentuk di atas akan menjadi :

\begin{array}{rcl}2.a_1+3.a_2+4.a_3+\ldots+n.a_{n-1}+(n+1).a_n&=&(1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n)+(a_1+a_2+a_3+\ldots+a_{n-1}+a_n)\\&=&z+x\end{array}

Sehingga :

  • Banyaknya bilangan yang mengandung ‘1’ pada kasus 3 adalah 1.x=x
  • Banyaknya kemunculan karakter ‘1’ ada sebanyak x+z kali

Rumus Umum Untuk Menghitung Banyaknya Bilangan n-digit yang Mengandung Karakter ‘1’

Untuk mencari rumus umum banyaknya bilangan pengandung karakter ‘1’ akan kita gabungkan ketiga kasus :

\begin{array}{lll}p(n)&=&(y)+(8x)+(x)\\&=&9x+y\\&=&9(10^{n-1}-y)+y\\&=&9.10^{n-1}-9y+y\\&=&9.10^{n-1}-8y\end{array}

Karena y adalah banyaknya bilangan pada \overline{BCDE\ldots} yang tidak mengandung karakter ‘1’, maka nilai dari y adalah 9^{n-1}

Dengan mensubstitusikan y=9^{n-1} kita peroleh :

p(n)=9.10^{n-1}-8.9^{n-1}

Rumus di atas adalah rumus umum untuk mencari banyaknya bilangan n-digit yang mengandung karakter ‘1’ di dalamnya.

Rumus Umum Untuk Menghitung Kemunculan Karakter ‘1’ Pada Bilangan n-digit

Sama seperti sebelumnya, untuk mencari rumus umum kemunculan, akan kita gabungkan ketiga kasus :

\begin{array}{llll}f(n)&=&\mbox{Kasus 1}+\mbox{Kasus 2}+\mbox{Kasus 3}\\&=&(y)+(8z)+(x+z)\\&=&x+y+9z\\&=&10^{n-1}+9z&\mbox{Karena }x+y=10^{n-1}\\f(n)&=&10^{n-1}+9(f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1))&\mbox{Karena }z=g(n-1)=f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)\end{array}

Kita peroleh rumus umum untuk mencari f(n). Mari kita cicip rumus kita :

\begin{array}{lll}f(1)&=&1\\\\f(2)&=&10^{2-1}+9(f(1))\\&=&10^1+9.1\\&=&19\\\\f(3)&=&10^{3-1}+9(f(1)+f(2))\\&=&10^2+9(1+19)\\&=&280\\\\f(4)&=&10^{4-1}+9(f(1)+f(2)+f(3))\\&=&10^3+9(1+19+280)\\&=&3700\\\\&&\cdots\end{array}

Walaupun rumus ini dapat memberikan hasil perhitungan dengan benar, namun rumus ini kurang ‘pas’ untuk diandalkan karena rumus ini bersifat rekursif dan sangat tergantung pada hasil-hasil perhitungan pada digit-digit sebelumnya.

Sekarang akan kita coba untuk memodifikasi rumus ini menjadi sedikit lebih baik. Perhatikan beberapa aljabar di bawah ini :

\begin{array}{rll}f(1)+f(2)&=&f(1)+10^1+9(f(1))\\&=&10^1+10(f(1))\\&=&10^1(1+f(1))\end{array}

\begin{array}{rll}f(1)+f(2)+f(3)&=&f(1)+f(2)+10^2+9(f(1)+f(2))\\&=&10^2+10(f(1)+f(2))\\&=&10^2+10.10^1(1+f(1))\\&=&10^2+10^2(1+f(1))\\&=&10^2(1+1+f(1))\end{array}

\begin{array}{rll}f(1)+f(2)+f(3)+f(4)&=&f(1)+f(2)+f(3)+10^3+9(f(1)+f(2)+f(3))\\&=&10^3+10(f(1)+f(2)+f(3))\\&=&10^3+10.10^2(1+1+f(1))\\&=&10^3+10^3(1+1+f(1))\\&=&10^3(1+1+1+f(1))\end{array}

dst…

\begin{array}{rll}f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)&=&10^{n-2}(1+1+1+\ldots+1+1+f(1))\\&=&10^{n-2}(n-2+f(1))\\&=&10^{n-2}(n-2+1)\\&=&10^{n-2}(n-1)\end{array}

Catatan : Aljabar di atas bukan pembuktian matematika yang sah. Walaupun demikian, pola aljabar di atas akan terus berulang-ulang dan hasilnya akan sama seperti yang ada di atas. Pembuktian matematis yang sah diserahkan kepada pembaca.

Sekarang, kita dapat menghitung f(n) dengan mudah, tanpa harus rekursif lagi

\begin{array}{lll}f(n)&=&10^{n-1}+9(f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1))\\&=&10^{n-1}+9.10^{n-2}.(n-1)\\&=&10.10^{n-2}+9.10^{n-2}.(n-1)\\&=&10^{n-2}(10+9.(n-1))\\&=&10^{n-2}(10+9n-9)\\f(n)&=&10^{n-2}(9n+1)\end{array}

Rumus yang terakhir ini adalah rumus yang kita inginkan. Rumus ini mampu “loncat” langsung ke digit yang kita inginkan tanpa harus menghitung satu persatu setiap digit mulai dari 1, 2, 3, …, sampai n-1.

Jawaban Atas Pertanyaan

Terkait dengan pertanyaan yang diajukan di awal artikel.

  1. Banyaknya bilangan di dalam himpunan tersebut yang mengandung karakter ‘1’ ada sebanyak :
    \begin{array}{lll}p(1)+p(2)+p(3)+1&=&(9.10^0-8.9^0)+(9.10^1-8.9^1)+(9.10^2-8.9^2)+1\\&=&(9.1-8.1)+(9.10-8.9)+(9.100-8.81)+1\\&=&(9-8)+(90-72)+(900-648)+1\\&=&1+18+252+1\\&=&272\end{array}
  2. Banyaknya kemunculan karakter ‘1’ ada sebanyak :
    \begin{array}{lll}f(1)+f(2)+f(3)+1&=&(10^{1-2}.(9.1+1))+(10^{2-2}.(9.2+1))+(10^{3-2}.(9.3+1))+1\\&=&(10^{-1}.(9+1))+(10^0.(18+1))+(10^1.(27+1))+1\\&=&(10^{-1}.10)+(1.19)+(10.28)+1\\&=&1+19+280+1\\&=&301\end{array}

Catatan : Perhatikan bahwa dalam soal di atas penulis mengasumsikan bahwa 1 dan 1000 diikutsertakan dalam perhitungan (inclusive). Dengan demikian rentang 1-1000 melibatkan 3 buah digit, yaitu digit 1, digit 2, dan digit 3 plus angka 1000 itu sendiri.

Angka 1 pada perhitungan di atas datang dari angka 1000 yang banyaknya ada 1 dan jelas sekali mengandung karakter ‘1’ di dalamnya.

The Code giveth, The Code Taketh away

Tinggalkan sebuah Komentar »

Belum ada komentar.

RSS feed for comments on this post. TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Blog di WordPress.com.

%d blogger menyukai ini: