Seri berfikir kombinatorik
BANYAKNYA KOTAK YANG DAPAT DIBENTUK DALAM GRID m x n Oleh: Sutopo Jurusan Fisika FMIPA UM
[email protected]
Ditulis pada sekitar bulan April 2011. Diunggah pada 3 Desember 2011
Problem Hitung banyaknya kotak yang dapat dibentuk dalam grid: 2x2, 3x3, dan secara umum ×
Pembahasan Cara 1 Banyaknya kotak (persegi atau persegi-panjang) yang dapat dibentuk dalam grid 2 x 2: adalah Jenis/ukuran
bentuk
Jumlah
2x2
Grid semula
2x1
A C
1x2
A B
1x1
Masingmasing kotak
Dari grid 3 x3 :
ukuran kotak 3x3 3x2 3x1 2x3 2x2 2x1 1x2 1x1 Jumlah
A D G
B E H
2
C D
2
1 2 = 3 2 4 = 6 Jadi, banyaknya kotak yang dihasilkan sebanyak 9 buah
4
C F I
Kotak-kotak yang dihasilkan Grid asli (keseluruhan) (A-D-G|B-E-H), (B-E-H|C-F-I) (A-D-G), (B-E-H), (C-F-I) (ABC|DEF), (DEF|GHI) (A-D-B-E), (B-C-E-F), (D-E-G-H), E-F-H-I) (A-D), (D-G), (B-E), (E-H), (C-F), (F-I) (AB), (BC), (DE), (EF), (GH), (HI) Masing-masing kotak dari A s.d I
Sutopo, Jurusan Fisika UM
B D
Ada empat macam (berarti 2x2) kotak, masing-masing sebanyak 1, 2, 2, 4 buah.
1
B D
A C
1
jumlah 1 2 3 2 4 6 6 9 36 Banyaknya kotak dalam grid mxn
Seri berfikir kombinatorik Ada 9 macam ukuran, seperti dinyatakan pada kolom pertama. Banyaknya kotak untuk setiap jenis/ukuran kotak dapat ditata dalam matriks berikut. p=3 p=2 p=1 Jumlah ke kanan ↓ ↓ ↓ Lebar = 3→ 1 2 3 = 6, Jumlah kotak berlebar 3 Lebar = 2→ 2 4 6 = 12, Jumlah kotak berlebar 2 Lebar = 1→ 3 6 9 = 18, Jumlah kotak berlebar 1 Jumlahkotak yang dapat dibentuk = 36
Berdasarkan pola yang diperoleh dari kedua kasus tersebut, diyakini bahwa banyaknya kotak yang dapat dibuat dari grid n x n adalah sebanyak jumlahan seluruh bilangan dalam matriks ukuran n x n dengan elemen pada baris pertama: 1, 2, 3, …, n, pada baris kedua: 2, 4, 6, …, 2n, dst Banyaknya kotak yang diperoleh dari grid 4x4 adalah:
p=4 1 2 3 4
p=3 2 4 6 8
p=2 p=1 3 4 = 6 8 = 9 12 = 12 16 = Banyaknya kotak =
keterangan Banyaknya kotak dengan lebar 4 Banyaknya kotak dengan lebar 3 Banyaknya kotak dengan lebar 2 Banyaknya kotak dengan lebar 1
10 20 30 40 100
Banyaknya kotak yang diperoleh dari grid 5x5 adalah:
p=5 ↓ 1 2 3 4 5
p=4 ↓ 2 4 6 8 10
p=3 ↓ 3 6 9 12 15
p=2 p=1 ↓ ↓ 4 5 = 15 8 10 = 30 12 15 = 45 16 20 = 60 20 25 = 75 Banyaknya kotak = 225 ×
Banyaknya kotak yang diperoleh dari grid
Banyaknya kotak dengan lebar 5 Banyaknya kotak dengan lebar 4 Banyaknya kotak dengan lebar 3 Banyaknya kotak dengan lebar 2 Banyaknya kotak dengan lebar 1
Banyaknya kotak dengan: ||
n −1 −2 −3
Panjang (p) = −1 n
1 2 3 4 . . .
1
…
1
2 4 6 8
3 6 9 12
4 8 12 16
5 10 15 20
… … … …
n 2n 3n 4n
2
3
4
5
…
. . .
−2
. . .
−3
. . .
−4
. . .
. … .
Jumlah ke kanan (banyaknya kotak dengan lebar tertentu dan panjang dari 1 s.d ): (1 + 2 + 3 + 4 + 5 + … +
) =
( + 1)/2
2(1 + 2 + 3 + 4 + 5 + … +
) = 2 ( + 1)/2
3(1 + 2 + 3 + 4 + 5 + … +
) = 3 ( + 1)/2
4(1 + 2 + 3 + 4 + 5 + … +
) = 4 ( + 1)/2
. … .
Jumlah kotak total = Sutopo, Jurusan Fisika UM
adalah:
(1 + 2 + 3 + 4 + 5 + … +
) =
( + 1)/2
(1 + 2 + 3 + … +
) ( + 1)/2 =
( + 1) /4
2
Banyaknya kotak dalam grid mxn
Seri berfikir kombinatorik
Cara 2: Cara induksi Grid 1x1 2x2 3x3 4x4 . . .
kotak Pola banyaknya kotak yang terbentuk 1 1 = 1 9 3 = (1 + 2) 36 6 = (1 + 2 + 3) 100 10 = (1 + 2 + 3 + 4) . . .
nxn
. . .
= (1 + 2 + 3 + 4 + … + n) =
(
)
Pola alternatif 1 12 123 1234 . . .
1 23…n =
(
)
Cara3: dengan metode kombinatorik 1. Cara pertama. Suatu kotak (persegipanjang) ditentukan oleh dua garis horizontal dan dua garis vertical. Dalam grid yang panjangnya ada + 1 garis, sehingga banyaknya cara membuat dua garis +1 vertical adalah . Demikian juga, banyaknya cara membuat dua garis horizontal dalam grid 2 +1 yang lebarnya m adalah . Setiap pasang garis vertical yang tercipta dapat dipasangkan 2 dengan sebarang pasangan garis horizontal untuk menghasilkan suatu persegipanjang. Karena itu, +1 +1 banyaknya persegipanjang yang dapat dibuat dalam grid × adalah × . 2 2 2. Cara kedua: mengungkapkan kembali Cara1 (di awal pembahasan) dengan bahasa kombinatorik sekaligus menghilangkan kesan bahwa cara tersebut bersifat induktif semata. ( Secara permukaan, cara tersebut memang terkesan induktif) Dalam grid × terdapat × kotak satuan. Dari sejumlah kotak satuan tersebut dapat dibuat berbagai macam persegipanjang dengan ukuran 1 × 1 s.d × . ( − ) Banyaknya cara membuat kotak dengan panjang satuan, = 1, 2 , . . , adalah ( − + 1) cara yang dapat dijelaskan sebagai berikut. Jika pengambilan kolom untuk yang pertamakalinya dilakukan dari kolom pertama (tentu saja harus sampai kolom ke- ), maka terdapat ( − ) kolom yang masih belum terpakai. Berarti masih ada ( − ) cara baru untuk mengambil kolom secara berurutan. Jadi, banyaknya cara membuat kotak dengan panjang satuan sama dengan ( − ) ditambah 1 (yaitu, pengambilan kolom untuk yang pertama kalinya). TERBUKTI
Banyaknya kotak yang panjangnya meliputi semua ukuran panjang yang mungkin, yaitu dari 1 s.d , adalah: (
Sutopo, Jurusan Fisika UM
)= 3
( − + 1) Banyaknya kotak dalam grid mxn
Seri berfikir kombinatorik
Dengan argumen yang sama, banyaknya kotak yang lebarnya meliputi semua ukuran lebar yang mungkin, yaitu dari 1 s.d , adalah: (
(
− + 1)
Karena kotak yang panjangnya satuan bisa memiliki berbagai ukuran lebar satuan, maka total kotak yang panjangnya satuan sebanyak: ( = ,
)=
)=
( − + 1)(
= 1, 2, … ,
− + 1)
Jadi, total kotak dengan berbagai ukuran panjang dan lebar yang mungkin adalah sebanyak: =
= =
= = =
( − + 1)(
( − + 1) × ( + 1) − ( + 1) × 2
− + 1)
(
− + 1)
( + 1) × 2 (
(
+ 1) −
(
+ 1) 2
+ 1) 2
( + 1)! ( + 1)! ( + 1)! ( + 1)! × = × ( − 1)! 2! ( − 1)! 2! ( + 1 − 2)! 2! ( + 1 − 2)! 2! +1 × 2
+1 . 2
Jadi, banyaknya persegipanjang yang dapat dibuat dalam grid
×
adalah
+1 × 2
+1 2
Cacatan Metode kombinatorik yang dipaparkan pada cara kedua tersebut dapat digunakan pula untuk menghitung banyaknya kotak dengan ukuran tertentu yang dapat dibentuk dalam grid ukuran tertentu tersedia. Misal:
Banyaknya persegipanjang berukuran × yang dapat dibentuk dalam grid berukuran dengan diambil dari dan diambil dari adalah ( , )=(
Sutopo, Jurusan Fisika UM
× ,
− + 1)( − + 1)
4
Banyaknya kotak dalam grid mxn
Seri berfikir kombinatorik
×
Banyaknya persegi yang dapat dibentuk dalam grid berukuran
⌊ , ⌋
(
− =
− )=
( ,
− + 1)( − + 1) =
,
adalah
⎧ ⎪
(
⎨ ⎪ ⎩
( − + 1) ;
− + 1) ;
≤ ≤
Kedua kemuningkan penjumlahan tersebut menghasilkan formulasi yang sama sebagai berikut. Ambil = , maka: (persegi) =
(
− + 1) =
=
(
+ 1)(2 6
+ 1)
Jika < maka rumus tersebut langsung dapat digunakan, sebaliknya jika tersebut harus digunakan dengan menganti dengan .
>
maka rumus
Ungkapan tersebut dapat dimodifikasi menjadi
(persegi) =
(
+ 1)(2 6
+ 1)
(
=
=
1 3
( + 1)! (2 + 1)! + 1) 2 + 1 × = × ( − 1)! 2! (2 )! 3 2 3 +1 2
2
+1 . 1
Contoh (1) Dalam grid 10 × 15, berapa banyaknya kotak (persegipanjang) dengan ukuran 2 × 5 yang dapat dibentuk? (2) Berapa banyaknya persegi yang dapat dibuat dalam grid (a) 10 × 15? (b) 10 × 10? (c) 15 × 15? Jawab (1) Jawaban atas pertanyaan (1) tersebut bergantung pada definisi kotak berukuran 2 × 5 tersebut. Jika 2 × 5 dimaksudkan sebagai kotak yang panjangnya 2 satuan (dari 10 kotak dalam grid yang tersedia) dan lebarnya 5 satuan (dari 15 kotak dalam grid yang tersedia), maka banyaknya kotak adalah (10 − 2 + 1)(15 − 5 + 1) = 99. Jika 2 × 5 dimaksudkan sebagai kotak yang panjangnya 2 satuan (dari 15 kotak dalam grid yang tersedia) dan lebarnya 5 satuan (dari 10 kotak dalam grid yang tersedia), maka banyaknya kotak adalah (15 − 2 + 1)(10 − 5 + 1) = 84. Jika yang dimaksud adalah kedua-duanya, yaitu 2 × 5 atau 5 × 2, maka jawabnya adalah 99 + 84 = 183. Sutopo, Jurusan Fisika UM
5
Banyaknya kotak dalam grid mxn
Seri berfikir kombinatorik (2) Berapa banyaknya persegi yang dapat dibuat dalam grid (a) 10 × 15? (b) 10 × 10? (c) 15 × 15? ( = ) = ∑ ( − + 1) = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 1 = 385. a) Atau
=
= ×
×
× 21 = 385
b) Sama dengan jawaban a) c)
( = )=∑ =
( − + 1) = 15 + 14 + ⋯ + 1 = = ×
×
×
×
= 1.240. Atau
× 31 = 1.240.
Catatan: Tulisan ini ditulis berdasarkan pemikiran logis semata, tidak merujuk pada kaedah/teorema matematika tertentu, karena penulis memang tidak tahu teori-teori itu, jika memang ada.
Sutopo, Jurusan Fisika UM
6
Banyaknya kotak dalam grid mxn
