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

Oktober 18, 2010

Berani Taruhan?

Filed under: Brain Teaser, Matematika, Peluang — Hendra Jaya @ 3:53 am

Problem

Di dalam sebuah kelompok yang terdiri dari 50 orang secara acak.
Berapa peluang, minimal 2 orang, dari anggota kelompok ini memiliki tanggal dan bulan lahir yang sama (abaikan tahun lahir)?

Di-dedikasikan untuk : Dedek tercinta :oops:, Nurul Retno Nurwulan yang ulang tahun tepat satu hari sebelum artikel ini ditulis.

Pembahasan

Jika A = “Tidak ada dari ke-50 orang ini yang tanggal lahirnya kembar”
Maka B = “Ada, minimal dua orang, dari 50 orang ini yang tanggal lahirnya kembar”
Relasi antara A dan B adalah : B=\neg A. Baca : B adalah negasi dari A.

Perhatikan bahwa Brain Teaser ini meminta kita untuk mencari peluang B, bukan peluang A.

Sekarang, jika :

P_{50} : “Peluang 50 dari ke-50 orang ini tanggal lahirnya kembar”
P_{49} : “Peluang 49 dari ke-50 orang ini tanggal lahirnya kembar”
P_{48} : “Peluang 48 dari ke-50 orang ini tanggal lahirnya kembar”

P_{2} : “Peluang 2 dari ke-50 orang ini tanggal lahirnya kembar”
P_{1} : “Peluang 1 dari ke-50 orang ini tanggal lahirnya kembar” alias “tidak ada yang tanggal lahirnya kembar”

Maka P_{1}+P_{2}+P_{3}+...+P_{48}+P_{49}+P_{50}=1.

Lebih jauh lagi :

\begin{array}{lll}A&=&P_{1}\\B&=&P_{2}+P_{3}+...+P_{48}+P_{49}+P_{50}\\&=&1-A\end{array}

Jika kita asumsikan 1 tahun = 365 hari.
Isi kelompok = 0 orang. Peluang tanggal lahir orang pertama belum “muncul” adalah \frac{365}{365}
Isi kelompok = 1 orang. Peluang tanggal lahir orang kedua belum “muncul” adalah \frac{364}{365}
Isi kelompok = 2 orang. Peluang tanggal lahir orang ketiga belum “muncul” adalah \frac{363}{365}
Isi kelompok = 3 orang. Peluang tanggal lahir orang keempat belum “muncul” adalah \frac{362}{365}

Isi kelompok = 48 orang. Peluang tanggal lahir orang ke-empatpuluhsembilan belum “muncul” adalah \frac{317}{365}
Isi kelompok = 49 orang. Peluang tanggal lahir orang ke-limapuluh belum “muncul” adalah \frac{316}{365}

Peluang kejadian ini (A) terjadi adalah \frac{365}{365}.\frac{364}{365}.\frac{363}{365}.\frac{362}{365}...\frac{317}{365}.\frac{316}{365}=0.02962642042201160

Dengan demikian peluang munculnya kejadian B adalah : B=1-A=1-0.02962642042201160=0.97037357957798840
Atau jika dinyatakan dalam persentase, peluang munculnya kejadian B adalah 97.04%
Atau jika dinyatakan dalam istilah sehari-hari : “Dalam 100 kali taruhan, saya akan menang sekitar 97 kali!”.

Intermezzo

Jika pembaca bertaruh sebanyak 100 kali setiap harinya, dengan besaran Rp. 1.000 tiap putaran. Maka pembaca sangat mungkin membawa pulang uang sekitar 90 ribu tiap harinya (anggap saja kalah 5 kali). Jika kegiatan ini pembaca lakukan setiap harinya, maka dalam satu bulan pembaca akan menghasilkan uang sekitar Rp. 2.700.000. Angka ini – setahu penulis – lebih besar dari gaji PNS golongan 3A di daerah manapun departemen apapun di Indonesia.

Sangat sulit dipercaya. Tetapi angka-angka ini tidak direkayasa dan murni matematika. Tanpa trik.

Peringatan Penulis : Berjudi itu dilarang oleh pemerintah dan agama.

Lottery

Buat situs web atau blog gratis di WordPress.com.