- Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali saja. Buktikan dengan induksi matematik bahwa jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah n(n – 1)/2.
Solusi:
Soal ini dapat diselesaikan dengan
menggunakan metode induksi matematika yang dirampatkan (generik), yakni untuk
membuktikan bahwa untuk n >= 2,
maka jumlah jabat tangan yang terjadi di antara n orang tamu adalah n(n
– 1)/2. Nilai n adalah minimal 2
karena jabat tangan hanya dapat terjadi jika terdapat minimal 2 orang tamu.
Basis
Induksi : untuk n = 2, maka jumlah jabat tangan yang
terjadi adalah 2(2-1)/2 = 1. Hal ini jelas benar karena untuk 2 orang tamu,
jabat tangan yang terjadi hanya sekali.
Langkah
induksi : andaikan untuk n >= 2 pernyataan bahwa “jumlah jabat
tangan yang terjadi sebanyak n(n – 1)/2” adalah benar (hipotesis
induksi). Kita harus menunjukkan bahwa jumlah jabat tangan yang terjadi di
antara n + 1 orang tamu adalah (n+1)((n + 1) - 1)/2 atau n(n+1)/2.
Hal ini dapat diselesaikan sebagai berikut:
Untuk n
orang tamu, jumlah jabat tangan yang terjadi adalah n(n – 1)/2 (dari
hipotesis induksi)
Untuk n
+ 1 orang, jumlah jabat tangan yang terjadi haruslah berupa jumlah jabat tangan
n orang tamu ditambah jabat tangan
yang dilakukan tamu ke-(n + 1). Tamu
yang ke-(n + 1) ini akan berjabat
tangan sebanyak n kali dengan n orang tamu lainnya (masing-masing
sekali) sehingga jumlah jabat tangan keseluruhan adalah
n(n – 1)/2 + n =
n(n
– 1)/2 + 2n/2
= (n2 – n + 2n)/2
= (n2 + n)/2
= n(n + 1)/2
Karena langkah
basis dan langkah induksi keduanya telah terbukti benar, maka terbukti bahwa jika ada n orang tamu,
maka jumlah jabat tangan yang terjadi adalah n(n – 1)/2.
- Misalkan m adalah bilangan bulat positif. Buktikan bahwa jika a mod m = b mod m, maka a º b (mod m).
Solusi:
a mod m = b mod m
a + k1
. m
= b + k2 . m
a = b
+ (k2 – k1) m
a – b
= (k2 – k1) m
yang berarti m habis membagi (a – b)
maka dapat dinyatakan bahwa
a º b (mod m) (terbukti)
- Nomor ISBN sebuah buku yang terbaca oleh bar code di toko buku adalah 0-07-053965-X. Apakah nomor ISBN tersebut sah? Jika tidak, bagaimana seharusnya?
Solusi:
Hal pertama yang harus
dilakukan adalah mengecek apakah benar karakter uji ISBN tersebut adalah X
(representasi angka 10).
mod 11 = karakter uji ……………………………….(1) sifat
karakter uji
= 1.0
+ 2.0 + 3.7 + 4.0 + 5.5 + 6.3 + 7.9 + 8.6 + 9.5
= 21 + 25 + 18 + 63 + 48 + 45
= 220…………………………………………………(2)
mod 11
= 220 mod 11 = 0…………………………...(3)
Solusi persamaan (3) adalah
0 (bukan 10) sehingga menunjukkan bahwa X
tidak memenuhi sifat karakter uji nomor ISBN di atas. Oleh sebab itu, karakter
uji ISBN di atas seharusnya bukan X,
melainkan 0.
Dengan demikian, nomor ISBN yang tepat adalah 0-07-053965-0.
- Nyatakan PBB(21, 45) sebagai kombinasi lanjar dari 21 dan 45.
Solusi:
PBB(45, 21) dicari
menggunakan algoritma Euclid:
45 = 2 (21) + 3
21 = 7 (3) + 0
Sisa
pembagian terakhir sebelum 0 adalah 3, maka PBB(45, 21) = 3
Substitusi
dengan persamaan–persamaan di atas menghasilkan:
3 = 45
– 2 (21)
yang merupakan kombinasi
lanjar dari 45 dan 21.
- Perlihatkan (bukan menghasilkan) bahwa 15 adalah balikan dari 7 (mod 26).
Solusi:
PBB(26, 7) dicari menggunakan algoritma Euclid:
26 =
3 (7) + 5
7 =
1 (5) + 2
5 =
2 (2) + 1
2 =
2 (1) + 0
Sisa pembagian terakhir sebelum 0 adalah 1, maka
PBB(26, 7) = 1, yang berarti 7 (mod 26) memang mempunyai balikan.
Untuk memperlihatkan bahwa 15 adalah balikan dari
7 (mod 26) maka harus diperlihatkan bahwa:
7 (15) ≡
1 (mod 26)
yaitu memperlihatkan bahwa:
7
(15) mod 26 = 1 mod 26
ruas kiri:
1 mod 26 =
1
ruas kanan:
7 (15) mod 26 =
105 mod 26
=
1
karena ruas kiri sama dengan ruas kanan maka terlihat bahwa 15 adalah balikan dari 7
(mod 26).
Atau:
7 (15) ≡ 1 (mod 26)
karena
7
(15) – 1 = 104 habis membagi 26 (yaitu, 104/26 = 4)
0 Komentar