[solved] Kelipatan yang terdiri dari 0 dan 1

Ga sengaja ketemu soal di papan tulis kampus :D

Buktikan, untuk setiap n anggota bilangan asli (n ∈ {1, 2, 3, …}) ada kelipatan dari n yang setiap digitnya hanya terdiri dari angka 0 atau 1 !

(mis. 10101 adalah kelipatan 3, 1111110 adalah kelipatan 7, 1000 adalah kelipatan 8, dll)

Keliatannya bingung ya gimana cara membuktikannya? Ternyata, tidak terlalu sulit! Thanks buat temen saya yang dewa matematika, saya bisa cukup ngerti dengan ide pembuktiannya :D

Pembuktian

Misalnya kita definisikan suatu himpunan A yang anggotanya adalah bilangan bulat yang hanya terdiri dari angka 1, sehingga

\[ A = \{1, 11, 111, 1111, ...\} \]

lalu, kita definisikan lagi sebuah himpunan B yang anggotanya adalah hasil modulo dari setiap anggota himpunan A dengan n (sebuah bilangan asli, sesuai dengan definisi dari soal), sehingga

\[ B = \{1 \mod n, 11 \mod n, 111 \mod n, 1111 \mod n, ...\} \]

perhatikan bahwa nilai dari $B_i = A_i \mod n$ itu selalu berada dalam range [0..n -1], sehingga hanya terdapat n buah nilai yang mungkin untuk Bi.

Oleh karena hanya ada n buah nilai yang mungkin untuk B, maka diantara n+1 buah anggota B pasti ada yang sama. Dengan kata lain ada p dan q dengan p < q < n+1, p dan q bilangan asli sehingga Bp = Bq.
\[B_p = B_q\]
\[A_p \mod n = A_q \mod n\]
berdasarkan sifat dari modulo, berlaku
\[(A_p - A_q) \mod n = B_p - B_q = 0\]
karena $(A_p - A_q) \mod n = 0 \displaystyle$ maka  $A_p - A_q \displaystyle $ adalah kelipatan dari n.
Dan karena setiap anggota A merupakan bilangan yang hanya terdiri dari angka 1, maka $A_p - A_q \displaystyle$ merupakan bilangan yang hanya terdiri dari angka 0 dan 1. (terbukti)

Kenalan dengan Matematika Diskrit

Karena kata orang tak kenal maka tak sayang dan tak sayang berarti tak belajar… (:P) Pada postingan ini kami akan membahas tentang sebuah cabang ilmu dari Matematika yaitu Matematika Diskrit. Sebenarnya apa itu matematika diskrit dan apa aja sih yang dibahas di dalamnya?

Yuk, Monggo dicermati.. :D

Matematika diskrit merupakan salah satu cabang yang khusus mempelajari objek-objek diskrit.

Sesuatu disebut sebagai objek diskrit apabila ia terdiri dari sejumlah elemen berhingga yang berbeda serta elemen-elemennya tidak kontinu. Contohnya: himpunan bilangan bulat (integer). Beda ‘kan dengan bilangan riil yang merupakan objek yang kontinu?

Secara garis besar sih, matematika diskret memang mempelajari tentang logikanya matematika. (Beda dewngan kalkulus yang lebih banyak belajar tentang aljabarnya matematika). Karena itulah Matematika Diskrit wajib dikuasai oleh setiap mahasiswa yang mengambil studi dalam rumpun computer science (Ilmu Komputer, Teknologi Informasi, Teknik Informatika, Sistem Informasi, Telekomunikasi, dll) . Matematika diskrit akan menjadi dasar dari pembelajaran algoritma, struktur data, basis data, jaringan komputer, keamanan komputer, sistem operasi, teknik kompilasi, dan teman-temannya.

Selain logika matematika dan algoritma, yang dipelajari dalam matematika diskrit antara lain: himpunan, matriks, fungsi, induksi matematika, Aljabar Boolean, Otoma dan teori bahasa formal, dan lain-lain.

Kenapa Matematika Diskret itu penting dipelajari dalam computer science? Karena … masalah-masalah seperti berapa jumlah kombinasi password yang mungkin dari sekian karakter, banyak string biner, dan lain-lain akan sangat membutuhkan matematika diskrit agar tidak kesulitan dalam mempelajari kuliah lain dalam rumpun computer science.

Nah, sekian perkenalan tentang matematika diskret. Pada kesempatan selanjutnya, kita akan membahas tentang Logika Proposisi, Logika Predikat dan mengenal apa itu Pohon Semantik dan cara kerjanya. Jadi, ikuti terus perkembanganya ya! :)

Lebih Baik Dari Kemarin!

Mungkin kita sering mendengar kutipan berikut

Barang siapa yang hari ini lebih baik dari hari kemarin, maka ia adalah orang yang beruntung

baik dari hadist, perkataan sahabat, perkataan ahli, atau siapapun. Memang seberapa "baik" sih kalau kita berhasil melakukan nasihat tersebut? oke, coba kita lihat pernyataan ini dalam perspektif matematis

Asumsikan kita dapat secara konsisten meningkatkan diri kita (entah potensi, kemampuan atau sikap) 1% saja dari sebelumnya setiap harinya. Maka, kalau kemampuan awal kita adalah x, kemampuan kita pada hari berikutnya adalah x + 0.01x. Dan pada hari berikutnya, kemampuan kita adalah x + 0.01x + 0.01(x + 0.01x). Sehingga jika dibuat menjadi deret 

\[ U_n = x, x + 0.01x, x + 0.01x + 0.01(x + 0.01x), ...\]

atau dalam bentuk lain

\[ U_n = x, 1.01x, 1.01^2 x, ...\]

sehingga jika dibuat rumus deretnya

$\displaystyle U_n = 1.01^{n-1}x$ dengan $\displaystyle n = 1, 2, 3, ...$

Nah, kalau kita cukup konsisten bisa melakukannya selama 1 tahun alias 365 hari, maka kemampuan kita menjadi $\displaystyle 1.01^{(365-1)}x$ atau sekitar 37 kali lipat dari sebelumnya! Dan kalau kita bisa melakukannya selama 2 tahun, maka kemampuan kita menjadi $\displaystyle 1.01^{(730-1)}x$ atau sekitar 1400 kali lipat! Padahal, ini baru dengan asumsi kita meningkat 1% setiap harinya, belum kalau 2%, 5%, atau lebih!

Pada akhirnya, kita bertanya kembali pada diri kita: bisakah kita konsisten seperti deret?

Rumus Deret Fibonacci?

Tahu deret Fibonacci kan? Ya, deret yang nilai sukunya merupakan jumlah dari 2 suku sebelumnya, dengan suku pertama dan kedua adalah 1. Secara matematis deret Fibonacci didefinisikan sebagai

\[F_n=\left\{\begin{matrix} 0&; n=0  \\ 1&; n=1  \\F_{n-1}+F_{n-2}&; n>1\end{matrix}\right.\]

Atau Fn = 0, 1, 1, 2, 3, 5, 8, 13, ...

Biasanya suku dari sebuah deret dapat dicari dengan rumus. Contohnya deret 1, 3, 5, 7, ... suku-sukunya dapat dicari dari rumus deret Un = 2n -1. Lalu apakah deret Fibonacci juga punya rumus suku deret? Jawabannya ya, meskipun jelas tidak sesederhana rumus deret biasanya. Rumus suku Fibonacci terkenal dengan nama Binet's Formula, yaitu:

[tutorial] Turunan Implisit

Pernah ketemu kurva yang ribet seperti $x^3y - 5y^3 + 2x^2 + 5= 0$ dan perlu mencari gradien garis singgungnya di titik (0,1) misalnya? Persamaan semacam itu biasanya tidak bisa dibentuk menjadi y = ..., lalu bagaimana cara menentukan turunannya?

nah, untuk itulah dibutuhkan teknik yang namanya turunan implisit. Caranya gampang, cukup turunkan kedua sisi terhadap x, lalu jika ketemu y diturunkan terhadap x, ubah menjadi $\frac{dy}{dx}$, Manfaatkan pula penggunaan teorema rantai. Agar lebih mudah dimengerti, kita lihat langsung contohnya.