Berapa banyak angka yang mengandung 17 dibawah 100 miliar (1717 dihitung 1)?

byBerutu Brother - 1

JUMLAH ANGKA 17 DIBAWAH 100 M

Jadi pada kali ini ada pertanyaan dari salah satu pengguna Quora yaitu  berapa banyak angka yang mengandung 17 dibawah 100 miliar (1717 dihitung 1)? Waw sepertinya cukup mustahil.Simak jawaban berikut

oleh:

, mantan pengajar merangkap tukang sapu di Shinjuku Les (2018-2020)
Diperbarui 7 Jan ·

Wah, ini soal PR yah dek?? Siapa yang kasih soal ginian? Guru kamu?

Atau kamu cuman mau tau aja?

Soal ini kelihatannya sepele, tapi sebenarnya susah loh. Kalau soal ini dari guru kamu, belum tentu dia juga bisa. Atau mungkin, dia tidak mengantisipasi semua variasi kemungkinan angka yang bakal keluar.

Eniwei, berhubung saya baik, langsung saja ke jawabannya deh. Jadi, bilangan yang mengandung angka 17 yang kurang dari 100 miliar, jumlahnya ada ???????? set variasi bilangan.

Dan menghitung ini bukanlah perkara mudah. Kalau kamu bisa mendapatkan jawaban yang sama dengan saya, kamu bisa daftar seleksi Olimpiade Matematika.

Enihow, kalau kamu masih penasaran angka di atas itu keluarnya dari mana, berikut rinciannya.

Adapun bilangan yang dibentuk harus kurang dari 100 milyar, berarti angka maksimum adalah 99.999.999.999 (totalnya ada 11 digit di situ)

(1.) SATU DIGIT

Tidak ada bilangan 1 digit yang memuat angka 17

(2.) DUA DIGIT

Hanya ada 1 anggota, yaitu 17.

(3.) TIGA DIGIT

Ada dua pola bilangan, yaitu 17Y (total 10 anggota, karena Y bisa diisi dengan angka 0 sampai 9) dan Y17 (total 9 anggota, karena angka pertama tidak boleh NOL). Jadi jumlahnya ada 19 anggota.

(4.) EMPAT DIGIT

Ada 3 kemungkinan pola angka yang muncul :

  • 17YY : Y bisa diisi dengan angka 0 - 9 dan dua digit itu independen, jadi ada 1 × 10² = 100 variasi
  • Y17Y dan YY17 : digit pertama tidak bisa nol, sehingga 2 pola × 9 × 10 = 180 variasi
  • dua repetisi 17 : hanya ada satu kemungkinan, yaitu 1717.

Perhatikan bahwa pola pertama 17YY dan YY17 sama-sama berpeluang menghasilkan 1717. Artinya, pola berbeda bisa menghasilkan angka yang sama, dan ini tidak diperbolehkan.

Jadi, untuk 4 digit ada 100 + 180 - 1 = 279 variasi. (perhatikan, angkanya dikurang bukan ditambah)

(5.) LIMA DIGIT

A.) Tanpa Repetisi

  • 17.YYY : ada 1 × 10³ = 1.000 variasi
  • Y1.7YY, YY.17Y, YY.Y17 : 3 × 9 × 10² = 2.700 variasi

B.) Repetisi Dua Kali

  • 1717Y dan 17Y17 : ada 2 × 10 = 20 variasi
  • Y1717 : ada 9 variasi

Perhatikan juga bahwa pola 1717Y merupakan subset (bagian) dari 17YYY dan YY17Y ; pola 17Y17 merupakan bagian dari 17YYY dan YYY17 ; pola Y1717 merupakan bagian dari Y17YY dan YYY17. Jadi, untuk 5 digit ada 3.700 - 29 = 3.671 variasi.

(6.) ENAM DIGIT

A.) Tanpa Repetisi

  • 17Y.YYY : 1 × 10⁴ = 10.000 variasi
  • pola lainnya : 4 × 9× 10³ = 36.000 variasi

B.) Dua Repetisi

  • berawalan dengan 17 (171.7YY ; 17Y.Y17 ; 17Y.17Y) : 3 × 1 × 10² = 300
  • tidak berawalan dengan 17 (Y17.17Y ; Y17.Y17 ; YY1.717) : 3 × 9 × 10 = 270

C.) Tiga Repetisi

  • anggotanya hanya satu, yaitu 171.171

Sampai di sini sudah masuk ke teori himpunan, sehingga untuk 6 digit ada 46.000 - 570 + 1 = 45.431 variasi.

(7.) TUJUH DIGIT

A.) Tanpa Repetisi

  • 1.7YY.YYY : 1 × 10⁵ = 100.000 variasi
  • posisi lainnya : 5 × 9 × 10⁴ = 450.000 variasi

B.) Dua Repetisi

  • berawalan dengan 17 : 4 × 1 × 10³ = 4.000
  • tidak berawalan dengan 17 : 6 × 9 × 10² = 5400

C.) Tiga Repetisi

  • berawalan dengan 17 : pola 1.717.17Y ; 1.717.Y17 ; 1.7Y1.717 : 3 × 10 = 30
  • tidak berawalan dengan 17 : Y.171.717 : 9

Untuk 7 digit ada 550.000 - 9.400 + 39 = 540.639 variasi.

(8.) DELAPAN DIGIT

A.) Tanpa Repetisi

  • 17.YYY.YYY : 1 × 10⁶ = 1.000.000 variasi
  • posisi lainnya : 6 × 9 × 10⁵ = 5.400.000 variasi

B.) Dua Repetisi

  • berawalan dengan 17 : 5 × 1 × 10⁴ = 50.000
  • tidak berawalan dengan 17 : ₅C₂ × 9 × 10³ = 90.000

C.) Tiga Repetisi

  • berawalan dengan 17 : ₄C₂ × 1 × 10² = 600
  • tidak berawalan dengan 17 : ₄C₃ × 9 × 10 = 360

D.) Empat Repetisi

  • hanya ada satu anggota, yaitu 17.171.717

Jadi, untuk 8 digit, ada 6.400.000 - 140.000 + 960 - 1 = 6.260.959 variasi.

(9.) SEMBILAN DIGIT

A.) Tanpa Repetisi

  • 17Y.YYY.YYY : 1 × 10⁷ = 10.000.000 variasi
  • posisi lainnya : 7 × 9 × 10⁶ = 63.000.000 variasi

B.) Dua Repetisi

  • berawalan dengan 17 : 6 × 1 × 10⁵ = 600.000
  • tidak berawalan dengan 17 : ₆C₂ × 9 × 10⁴ = 1.350.000

C.) Tiga Repetisi

  • berawalan dengan 17 : ₅C₂ × 1 × 10³ = 10.000
  • tidak berawalan dengan 17 : ₅C₃ × 9 × 100 = 9.000

D.) Empat Repetisi

  • berawalan dengan 17 : 4 × 10 = 40
  • tidak berawalan dengan 17 : Y17.171.717 (ada 9 variasi)

Jadi, untuk 9 digit, ada 73.000.000 - 1.950.000 + 19.000 - 49 = 71.068.951 variasi.

(10.) SEPULUH DIGIT

A.) Tanpa Repetisi

  • 1.7YY.YYY.YYY : 1 × 10⁸ = 100.000.000 variasi
  • posisi lainnya : 8 × 9 × 10⁷ = 720.000.000 variasi

B.) Dua Repetisi

  • berawalan dengan 17 : 7 × 1 × 10⁶ = 7.000.000
  • tidak berawalan dengan 17 : ₇C₂ × 9 × 10⁵ = 18.900.000

C.) Tiga Repetisi

  • berawalan dengan 17 : ₆C₂ × 1 × 10⁴ = 150.000
  • tidak berawalan dengan 17 : ₆C₃ × 9 × 10³ = 180.000

D.) Empat Repetisi

  • berawalan dengan 17 : ₅C₃ × 1 × 10² = 1.000
  • tidak berawalan dengan 17 : 5 × 9 × 10 = 450

E.) Lima Repetisi

  • hanya ada satu anggota, yaitu 1.717.171.717

Jadi, untuk 10 digit, ada 820.000.000 - 25.900.000 + 330.000 - 1450 + 1 = 794.428.551 variasi.

(11.) SEBELAS DIGIT

A.) Tanpa Repetisi

  • 17.YYY.YYY.YYY : 1 × 10⁹ = 1.000.000.000 variasi
  • posisi lainnya : 9 × 9 × 10⁸ = 8.100.000.000 variasi

B.) Dua Repetisi

  • berawalan dengan 17 : 8 × 1 × 10⁷ = 80.000.000
  • tidak berawalan dengan 17 : ₈C₂ × 9 × 10⁶ = 252.000.000

C.) Tiga Repetisi

  • berawalan dengan 17 : ₇C₂ × 1 × 10⁵ = 2.100.000
  • tidak berawalan dengan 17 : ₇C₃ × 9 × 10⁴ = 3.150.000

D.) Empat Repetisi

  • berawalan dengan 17 : ₆C₃ × 1 × 10³ = 20.000
  • tidak berawalan dengan 17 : ₆C₄ × 9 × 100 = 13.500

E.) Lima Repetisi

  • berawalan dengan 17 : 5 × 1 × 10 = 50
  • tidak berawalan dengan 17 : Y1.717.171.717 (ada 9 variasi)

Jadi, untuk 11 digit, ada 9.100.000.000 - 332.000.000 + 5.250.000 - 33500 + 59 = 8.773.216.559 variasi.

Nah, sekarang tinggal dijumlah saja semuanya :

  • 11 digit : 8.773.216.559 bilangan
  • 10 digit : 794.428.551 bilangan
  • 9 digit : 71.068.951 bilangan
  • 8 digit : 6.260.959 bilangan
  • 7 digit : 540.639 bilangan
  • 6 digit : 45.431 bilangan
  • 5 digit : 3.671 bilangan
  • 4 digit : 279 bilangan
  • 3 digit : 19 bilangan
  • 2 digit : 1 bilangan
  • 1 digit : 0

Total : 9.645.565.060 bilangan. Kira-kira segitu.

>>>>>>

Saya akan coba pakai metode lain. Kombinasi-permutasi. Bilangan 4 digit atau 5 digit secara prinsip merupakan bilangan 11 digit yang beberapa digit awalnya bernilai nol. Saya akan gunakan sifat ini.

(1.) Bilangan Dengan Satu Angka 17

Jumlah variasi yang mungkin : 10 × 1 × 10⁹ = 10.000.000.000

(2.) Bilangan Dengan Dua Repetisi

Jumlah variasi yang mungkin : ₉C₂ × 10⁷ = 360.000.000

(3.) Tiga Repetisi

Jumlah variasi yang mungkin : ₈C₃ × 10⁵ = 5.600.000

(4.) Empat Repetisi

Jumlah variasi yang mungkin : ₇C₄ × 10³ = 35.000

(5.) Lima Repetisi

Jumlah variasi yang mungkin : ₆C₅ × 10 = 60

Total bilangan yang mungkin :

10.000.000.000 - 360.000.000 + 5.600.000 - 35.000 + 60 = 9.645.565.060 bilangan. Hasilnya sama persis, berarti perhitungan saya hasilnya [semoga] benar lah yah…. Kekurangan metode ini adalah bahwa metode ini tidak bisa mencari bilangan yang spesifik memiliki jumlah digit tertentu.

mabok kepalaku…. kaget pas lihat tanganku sendiri koq jarinya ada tujuh…

Jadi, demikianlah yang bisa saya sampaikan. Sekian dan terima gaji.


==========================================================================================================================================

selain cara di atas ternyata ada cara yang lebih keren lagi yaitu dengan menggunakan pemograman.Penasaran bagaimana caranya simak cara dari pengguna atau penulis kedua Quora berikut


oleh:

, belajar Rekayasa Perangkat Lunak di Institute of Systems Science, NUS (2007)
Dijawab 8 Jan

Saatnya jual diri…

Enaknya punya pacar programmer itu, walapun culun, kurang modis, dan tidak romantis, dia akan selalu siap menolong dengan senang hati kalau kamu dapat tugas sekolah / kuliah seperti ini. Bahkan sebelum kamu minta pun, mungkin dia akan menawarkan untuk membantu karena merasa tertantang.

Dan kalau kamu minta tolong di hari Sabtu, dia mungkin akan memilih tinggal di rumah untuk membantu, bukannya keluar minum² dengan teman²nya para pemabuk itu. Memang punya pacar programmer itu menenangkan hati, karena orangnya tidak neko². Mungkin karena itu Scott Adams bisa punya istri seperti ini ya… 🤔

Foto istri Scott Adams (pengarang Dilbert) hanya pemanis

Lah pertanyaannya kan tentang matematika Dul! Kok jadi ngelantur ke programming sih?

Eh iya… sabar… mari kita mulai dengan matematikanya dulu ya.

Seperti biasa, sebelum kita pecahkan masalah yg besar (100 milyar), kita mulai dengan masalah yg kecil dulu.

Berapa banyak angka yg mengandung "17" di bawah sepuluh (10 pangkat 1)?

Ya ndak ada, kalau pangkatnya (1) saya masukkan ke variabel n, jawabannya menjadi:

Untuk n = 1, jumlah angka yg mengandung "17" adalah 0

Berapa banyak angka yg mengandung "17" di bawah seratus (10 pangkat 2)?

Ya hanya satu, angka 17 itu sendiri.

Untuk n = 2, jumlah angka yg mengandung "17" adalah 1

Berapa banyak angka yg mengandung "17" di bawah seribu (10 pangkat 3)?

Di bawah 1000 itu berarti dari 0 sampai 999 ya. Hanya ada 2 kemungkinan posisi "17", di ujung kanan atau di ujung kiri.

Set #1: di ujung kanan ada 10 angka mengandung "17":

  1. 017 (di depan 17 saya letakkan 0 supaya seragam) 
  2. 117 
  3. 217 
  4. 317 
  5. 417 
  6. 517 
  7. 617 
  8. 717 
  9. 817 
  10. 917 

Set #2: geser "17" satu langkah ke kiri, menjadi di ujung kiri, ada 10 angka juga:

  1. 170 
  2. 171 
  3. 172 
  4. 173 
  5. 174 
  6. 175 
  7. 176 
  8. 177 
  9. 178 
  10. 179 

Untuk n = 3, jumlah angka yg mengandung "17" adalah 10 + 10 = 20

Berapa banyak angka yg mengandung "17" di bawah sepuluh ribu (10 pangkat 4)?

Set #1: tempatkan "17" di ujung kanan, hanya 2 angka di depan yg berubah dari 00 ke 99. Jadi ada 100 angka mengandung "17" untuk set #1

  1. 0017  
  2. .... 
  3. .... 
  4. 9917 

Set #2: geser "17" satu langkah ke kiri. Sekali lagi, ada 2 angka yg berubah (ujung kiri dan ujung kanan), dari 00 ke 99. Jadi ada 100 angka untuk set #2

  1. 0170 
  2. .... 
  3. .... 
  4. 0179 
  5. 1170 
  6. .... 
  7. .... 
  8. 1179 
  9. .... 
  10. .... 
  11. 9170 
  12. .... 
  13. .... 
  14. 9179 

Set #3: geser "17" satu langkah ke kiri. Sekali lagi, ada 2 angka yg berubah, dari 00 ke 99. Jadi ada 100 angka untuk set #3

  1. 1700 
  2. .... 
  3. .... 
  4. 1799 

Selesai? Belum, karena ada overlap.

  • Set #2 tidak mungkin overlap dengan set #1, karena angka ke-3 di set #1 selalu 1, dan angka ke-3 di set #2 selalu 7.
  • Set #3 tidak mungkin overlap dengan set #2, karena angka ke-2 di set #2 selalu 1, dan angka ke-2 di set #3 selalu 7.
  • Set #3 overlap dengan set #1 di angka 1717. Karena itu kita harus buang 1717 dari set #3, karena 1717 sudah disebut di set #1. Jadi sebenarnya set #3 hanya punya 99 angka.

Untuk n = 4, jumlah angka yg mengandung "17" adalah 100 + 100 + 99 = 299

Sampai di sini sudah kelihatan pola belum? Mungkin belum ya, kalau begitu kita lanjutkan dulu.

Berapa banyak angka yg mengandung "17" di bawah seratus ribu (10 pangkat 5)?

Set #1: seperti biasa, mulai dengan menempatkan "17" di ujung kanan. Yg berubah hanya 3 angka di ujung kiri, dari 000 sampai 999. Jadi ada 1000 angka mengandung "17" untuk set #1

  1. 00017 
  2. ..... 
  3. ..... 
  4. 99917 

Set #2: geser "17" satu langkah ke kiri. Mulai kelihatan pola nih… ada 1000 angka lagi untuk set #2

  1. 00170 
  2. ..... 
  3. ..... 
  4. 99179 

Set #3: geser "17" satu langkah ke kiri. Ada 1000 angka lagi untuk set #3

  1. 01700 
  2. ..... 
  3. ..... 
  4. 91799 

Set #4: geser "17" satu langkah ke kiri. Ada 1000 angka untuk set #4

  1. 17000 
  2. ..... 
  3. ..... 
  4. 17999 

Sekarang kita lihat ada overlap tidak.

  • Set #2 tidak mungkin overlap dengan set #1
  • Set #3 tidak mungkin overlap dengan set #2
  • Set #3 overlap dengan set #1 di 10 angka, jadi kita harus buang 10 angka berikut dari set #3. Set #3 hanya punya 990 angka sekarang.
  1. 01717 
  2. ..... 
  3. ..... 
  4. 91717 
  • Set #4 tidak mungkin overlap dengan set #3
  • Set #4 overlap dengan set #2 di 10 angka, jadi kita harus buang 10 angka berikut dari set #4. Set #4 hanya punya 990 angka sekarang
  1. 17170 
  2. ..... 
  3. ..... 
  4. 17179 
  • Set #4 overlap dengan set #1 di 10 angka, jadi kita harus buang 10 angka lagi dari set #4. Set #4 hanya punya 980 angka sekarang
  1. 17017 
  2. ..... 
  3. ..... 
  4. 17917 

Untuk n = 5, jumlah angka yg mengandung "17" adalah 1000 + 1000 + 990 + 980 = 3970

Hufff… udah ah, cape. Sekarang coba kita lihat polanya.

  • Untuk n = 4:
    • Jumlah angka di set #1 sama dengan 10 kali jumlah angka di set #1 dalam jawaban n = 3
      • 100 = 10 * 10
    • Jumlah angka di set #2 sama dengan 10 kali jumlah angka di set #2 dalam jawaban n = 3
      • 100 = 10 * 10
    • Jumlah angka di set #3 sama dengan 10 pangkat (n - 2) dikurangi jawaban untuk n = 2
      • 99 = 100 - 1
  • Coba kita verifikasi polanya dengan n = 5:
    • Jumlah angka di set #1 sama dengan 10 kali jumlah angka di set #1 dalam jawaban n = 4
      • 1000 = 10 * 100
    • Jumlah angka di set #2 sama dengan 10 kali jumlah angka di set #2 dalam jawaban n = 4
      • 1000 = 10 * 100
    • Jumlah angka di set #3 sama dengan 10 kali jumlah angka di set #3 dalam jawaban n = 4
      • 990 = 10 * 99
    • Jumlah angka di set #4 sama dengan 10 pangkat (n - 2) dikurangi jawaban untuk n = 3
      • 980 = 1000 - 20

Wahh… cucok! Kalau begitu pola di atas bisa disederhanakan menjadi:

Jumlah angka untuk n adalah:

  • 10 kali jumlah angka dalam jawaban (n - 1)
  • Ditambah 10 pangkat (n - 2)
  • Dikurangi jawaban untuk (n - 2)
  • Di mana n >= 2

Notasi matematikanya menjadi:

f(n)=10×f(n−1)+10(n−2)−f(n−2)

Oke… sekarang kita sudah punya rumusnya. Jadi untuk menghitung jumlah angka yg mengandung "17" di bawah 100 milyar kita harus menghitung jumlah angka yg mengandung "17" di bawah 10 milyar, 1 milyar, dan seterusnya?

Tidak usah dihitung manual. Programmer culun to the rescue!

Untuk menguji rumus di atas, saya tulis program blo'on dan lambat, tapi hasilnya pasti benar. Karena kerjanya hanya melakukan iterasi dari 0 sampai angka yg dituju (100, 1000, 10000, dsb), dan mengkonversikan angka tersebut ke String (deretan karakter). Kemudian cek apakah String "17" ada di dalam String angka tersebut.

Kalau program ini dijalankan 8 kali dengan input 1 sampai 8, hasilnya:

  1. n: 1, result: 0, runtime: 40ms 
  2. n: 2, result: 1, runtime: 38ms 
  3. n: 3, result: 20, runtime: 38ms 
  4. n: 4, result: 299, runtime: 41ms 
  5. n: 5, result: 3970, runtime: 51ms 
  6. n: 6, result: 49401, runtime: 89ms 
  7. n: 7, result: 590040, runtime: 366ms 
  8. n: 8, result: 6850999, runtime: 3434ms 

Pada saat n = 8 (mencari jumlah angka mengandung "17" di bawah seratus juta), program blo'on ini mulai megap². Perlu lebih dari 3 detik untuk mendapatkan jawaban.

Sekarang saya tulis program yg menghitung menggunakan rumus matematika di atas. Karena rumusnya hanya 1 baris, programnya juga sangat sederhana.

Kalau program ini saya jalankan 15 kali dengan input 1 sampai 15, hasilnya:

  1. n: 1, result: 0, runtime: 0ms 
  2. n: 2, result: 1, runtime: 0ms 
  3. n: 3, result: 20, runtime: 0ms 
  4. n: 4, result: 299, runtime: 1ms 
  5. n: 5, result: 3970, runtime: 0ms 
  6. n: 6, result: 49401, runtime: 0ms 
  7. n: 7, result: 590040, runtime: 0ms 
  8. n: 8, result: 6850999, runtime: 0ms 
  9. n: 9, result: 77919950, runtime: 0ms 
  10. n: 10, result: 872348501, runtime: 0ms 
  11. n: 11, result: 9645565060, runtime: 0ms 
  12. n: 12, result: 105583302099, runtime: 0ms 
  13. n: 13, result: 1146187455930, runtime: 0ms 
  14. n: 14, result: 12356291257201, runtime: 1ms 
  15. n: 15, result: 132416725116080, runtime: 1ms 

Hasil dari n = 1 sampai n = 8 sama dengan hasil program blo'on. Berarti rumus di atas benar yah. Dan ternyata menghitung sampai satu triliar (1000 triliun) hanya perlu seperseribu detik.

Karena pertanyaannya hanya 100 milyar, saya jalankan program blo'on dengan input 11 untuk verifikasi hasil. Hasilnya:

  1. n: 11, result: 9645565060, runtime: 3957643ms 

Begitulah hubungan antara programming dengan menyelesaikan masalah matematika. Saya kadang² melihat pertanyaan di Quora tentang hubungan antara matematika dan belajar programming. Kalau masalahnya sudah disederhanakan secara matematis, programnya akan jadi singkat, simple, dan elegan.

Saya harap jawaban ini juga bisa membantu memberi gambaran kepada adik² yg tertarik untuk mengambil jurusan Teknik Informatika / Software Engineering / Computer Science. Kerja kami itu ya seperti ini, meng-otomatisasi pekerjaan manual yg repetitif dan membosankan.

Saya juga berharap jawaban ini bisa membantu mempromosikan para programmer culun dan jomblo yg belum beruntung mendapatkan pasangan hidup. May cupid have mercy on all of us.

Sumber: Which Dilbert character are you?

Tags:

Berutu Brother

Saya blogger amatiran jadi maaf bila banyak kesalahan. Jujur saya tidak tahu apa itu cinta,tapi saya bisa merasakanya.

1 Komentar

Posting Komentar

Post a Comment

Lebih baru Lebih lama