...

BANYAKNYA DAERAH DALAM LINGKARAN

by user

on
Category: Documents
0

views

Report

Comments

Transcript

BANYAKNYA DAERAH DALAM LINGKARAN
Seri berfikir kombinatorik
2011
Banyaknya daerah dalam lingkaran yang dibentuk oleh
mengubungkan garis-garis yang n titik pada lingkaran
Oleh: Sutopo
Jurusan Fisika FMIPA UM
[email protected]
Ditulis pada sekitar bulan April 2011.
Diunggah pada 3 Desember 2011
Problem
Apabila n buah titik ditempatkan pada keliling lingkaran kemudian masing-masing
titik saling dihubungkan dengan suatu garis lurus, maka lingkaran itu akan terbagi
menjadi sejumlah daerah. Apabila tidak ada tiga garis yang berpotongan di satu
titik dalam lingkaran itu, berapa banyak daerah yang akan terbentuk?
Pembahasan
Langkah 1. Selidiki dulu pengaruh kehadiran sebuah titik baru terhadap formasi yang telah ada
(dihasilkan oleh sejumlah titik yang sebelumnya telah dipasang). Misalnya, titik Q ditambahkan pada
formasi yang telah dihasilkan oleh 4 titik, seperti pada gambar.





Garis pertama, 1, menambah satu daerah baru, tidak memotong garisgaris yang telah ada.
Garis kedua, 2, menambah 3 daerah baru, memotong 2 garis yang telah
ada, yaitu 13 dan 14.
Garis ketiga, 3, menambah 3 daerah baru, memotong 2 garis yang telah
ada, yaitu 14 dan 24.
Garis ke-4, 4, menambah satu daerah baru, tidak memotong garis-garis yang telah ada.
Jadi, banyaknya daerah baru yang diakibatkan oleh titik ke-5 adalah 8 daerah. Maka diperoleh
rumusan (5) = (4) + 8, dengan ( ) menyatakan banyaknya daerah yang dihasilkan oleh
titik.
Ada tiga hal penting yang ditunjukkan oleh percobaan tersebut, yaitu sebagai berikut.



Titik ke 5 menghasilkan 4 potong garis, diperluas: titik ke- menghasilkan ( − 1) potong garis.
Banyaknya daerah baru akibat masing-masing garis tersebut sama dengan banyaknya perpotongan
(di dalam lingkaran) garis itu dengan garis-garis yang sudah ada ditambah satu.
Banyaknya daerah yang dihasilkan oleh titik, adalah ( ) = ( − 1) + ( ), dengan ( )
menyatakan banyaknya daerah baru yang dihasilkan oleh titik ke- .
Sutopo, Fisika UM
1
Seri berfikir kombinatorik
2011
Langkah 2: mencari formula banyaknya titik potong
Berpijak pada hasil langkah pertama: (1) banyaknya daerah baru yang dihasilkan titik terakhir sama
dengan jumlahan dari banyaknya daerah yang dihasilkan masing-masing garis yang menghubungkan
titik itu dengan titik sebelumnya, dan (2) banyaknya daerah baru yang dihasilkan oleh suatu garis
ditentukan oleh banyaknya titik potong garis itu dengan garis-garis yang sudah ada, maka analis
difokuskan pada menghitung banyaknya titik potong tehadap suatu garis.
 Buat ( − 1) titik dan labeli secara berurutan dengan bilangan 1 s.d ( − 1).
Untuk memudahkan analisis, titik-titik tersebut tidak saling dihubungkan
terlebih dulu. (Garis-garis hubung akan dibuat secara bertahap pada saatnya
nanti). Tambahkan titik Q, sebagai titik ke- , di antara titik ke-1 dan titik ke( − 1). Lihat gambar di samping.
 Secara bertahap, titik Q dihubungkan dengan garis lurus ke titik-titik yang sudah
ada, sambil didata banyaknya titik potong dan daerah baru yang dihasilkan.
Gambar di samping menunjukkan cara menghitung banyaknya titik potong yang
dihasilkan garis 1 dan 2.
Terlihat bahwa:


Garis 1 tidak memotong garis manapun. Jika ( )menyatakan banyaknya titik potong, maka
( )= .
Garis 2 memotong semua garis dari titik 1 ke titik-titik: 3, 4, 5, …, ( − 1). Maka banyaknya titik
potong adalah ( − 1) − 2 = − 3. Jadi ( ) = − .
Jika dilanjutkan ke garis-garis berikutnya, diperoleh data sebagai berikut:

Garis 3 memotong:
o semua garis dari titik 1 ke titik-titik: 4, 5, 6, …, ( − 1); sebanyak ( − 4) garis
o dan semua garis dari titik 2 ke titik-titik: 4, 5, 6, …, ( − 1); juga sebanyak ( − 4) garis.
Jadi ( ) = ( − ).

Garis 4 memotong:
o semua garis dari titik 1 ke titik-titik: 5, 6, 7,…, ( − 1); sebanyak ( − 5) garis,
o semua garis dari titik 2 ke titik-titik: 5, 6, 7,…, ( − 1); sebanyak ( − 5) garis,
o semua garis dari titik 3 ke titik-titik: 5, 6, 7,…, ( − 1); sebanyak ( − 5) garis.
Jadi (

) = ( − ).
Secara umum diperoleh formula: (
Untuk =
Sutopo, Fisika UM
− 1, maka
) = ( − )( −
− );
=
( − 1) = 0 seperti yang diharapkan.
2
, , , … , ( − ).
Seri berfikir kombinatorik
2011
Langkah 3: mencari formula untuk ( ), yaitu daerah baru yang disumbangkan oleh titik ke-n
Banyaknya daerah baru yang dihasilkan oleh garis
(
adalah
) + 1 = ( − 1)( − 1 − ) + 1 = (2 − ) +
−
.
Maka banyaknya daerah baru yang diakibatkan oleh kehadiran titik Q (sebagai titik ke- ) adalah:
( )=
{(2 − ) +
(2 − ) +
}=
−
−
Dengan menggunakan formula:
(
=
+ 1)
dan
2
(
=
+ 1)(2
6
+ 1)
Maka
(
( ) = ( − 1)(2 − ) +
= ( − 1)(2 − ) +
=
(
)[
(
)!
=(
+ −6 +12]
6
+
)!
(
!(
)
+
(
)(
( −1)[3 −2 +2−1]
6
=
(
)!
=
)!
)[(
−1
+
1
)[ (
=
(
−5 +6)+6]
6
)
)(
]
)
+
( −1)[ +1]
= ( − 1) +
6
( −1)( −2)( −3)
−1
3
Langkah 4: mencari formula untuk ( ), rumus Rekursi
Langkah pertama telah menghasilkan formula ( ) = ( − 1) + ( ), dan langkah ke-3 telah
menghasilkan formula untuk ( ). Berdasarkan kedua formula tersebut, secara iteratif dapat
ditemukan ( ) untuk setiap jika ( − 1) telah diketahui. Karena (1) = 1, maka ( ) dapat
ditentukan dengan rumus rekursi berikut:
(1) = 1
( ) = ( − 1) +
Beberapa contoh:
G(2) = 1 + 1 + 0 = 2
G(3) = 2 + 2 + 0 = 4
G(4) = 4 + 3 + 1 = 8
Sutopo, Fisika UM
−1
+
1
−1
3
G(5) = 8 + 4 + 4 = 16
G(6) = 16 + 5 + 10 = 31
G(7) = 31 + 6 + 20 = 58
3
Seri berfikir kombinatorik
2011
Langkah 5: mencari formula langsung (tanpa rekursi) untuk ( )
Berdasarkan rumus rekursi tersebut dapat diturunkan formula umum ( ) sebagai berikut.
⎧
⎪⎧
⎪⎪
⎪
( )=
(1) + 0 + 0
1
3
⎨⎨
⎪
⎪⎪
⎪⎩
⎩
+
⎫
⎪
⎪
1
1
+
1
3
+
( )
( )
( )
(
⎫
⎪
⎪
2
2
+
+⋯ +
1
3 ⎬
⎬
⎪
⎪
⎪
⎪
⎭
⎭
−1
+
1
−1
3
)
Jika kurung-kurungnya dibuka, diperoleh deretan:
( ) = (1) + 0 + 0 + 1 + 1 + 2 + 2 + 2 + 2 + ⋯ +
1
3
1
3
1
3
1
3
−1
+
1
−1
3
Dengan mengamati suku-suku yang ada, rumusan tersebut dapat disederhanakan menjadi:
( ) = (1) +
1
+
3
=1+
−1+1
+
1+1
−1+1
=
+
+
.
0
2
4
3+1
Dalam menyelesaian penjumlahan tersebut telah digunakan formula: ∑
=
+1
.
+1
Jadi diperoleh formula akhir:
Banyaknya daerah yang dihasilkan oleh
( )=
0
+
2
titik maksimum sebanyak:
+
4
.
Mengapa maksimum? Karena rumusan tersebut diperoleh dengan asumsi tidak ada 3 atau lebih garis
yang berpotongan di satu titik di dalam lingkaran. Apa akibatnya jika ada 3 atau lebih garis yang seperti
itu? Perhatikan gambar di samping. Pada gambar kiri, garis
3 memotong garis 14 dan 25 di titik yang berbeda dan
secara keseluruhan memotong 4 garis yang sudah ada.
Akibatnya, kehadiran garis tersebut menambah 5 daerah
baru. Pada gambar kanan, di lain pihak, 3 memotong garis
14 dan 25 di titik yang sama sehingga secara keseluruhan
hanya menghasilkan 3 titik potong, dan menyumbang 4 daerah baru. Jadi, jika ada 3 garis yang
berpotongan di satu titik di dalam lingkaran, banyaknya daerah lebih sedikit daripada jika ketiga garis
tersebut tidak berpotongan di satu titik.
Sutopo, Fisika UM
4
Seri berfikir kombinatorik
2011
Cara lain
Persoalan tersebut juga bisa diselesaikan dengan membuat garis-garis secara berurutan dari titik 1 ke
titik-titik : 2, 3, …, ; dilanjutkan dari titik 2 ke titik-titik: 3, 4, …, ; (garis 21 sudah terbentuk
sebelumnya), dilanjutkan dari titik 3 ke titik-titik: 4, 5, …, ; (garis 31 dan 32 sudah terbentuk
sebelumnya), dst. Maka, banyaknya garis yang dibuat dari masing-masing titik tersebut dapat dirangkum
dalam table berikut.
Tabel 1. Banyaknya garis baru yang dibuat dari titik-titik 1, 2, dst
Titik asal
1
2
3
4
…
# garis
−1
−2
−3
−4
…
−
3
−
2
0
1
Ketika garis-garis itu dibuat:
2
 Garis-garis dari titik 1 tidak memotong garis manapun. Jadi
banyaknya daerah yang dihasilkan ketika itu sebanyak:
1 + 1 + 1 + … + 1 (sebanyak
−
1
kali) =
n
3
n-1
daerah
 Garis-garis dari titik 2, kecuali garis 23, memotong garis-garis
13, 14, 15, … , 1( − 1). Lihat gambar. Banyaknya titik potong dan
5
daerah baru yang dihasilkan masing-masing garis dapat didaftar
sebagai berikut.
o Garis 23 tidak memotong garis lain,→daerah baru yang dihasilkan: 1 daerah.
o Garis 24 memotong garis 13,→daerah baru yang dihasilkan: 2 daerah.
o Garis 25 memotong garis 13 dan 14 →daerah baru yang dihasilkan: 3 daerah.
o dst
o Garis 2 memotong garis-garis: 13, 14, … , 1( − 1), →daerah baru yang dihasilkan: − 2
daerah.
Banyaknya daerah yang disumbangkan oleh titik 2 adalah: 1 + 2 + 3 + … + ( − 2)
 Garis-garis dari titik 3, kecuali garis 34, memotong garis-garis 14, 15, … , 1( − 1) serta garis-garis
24, 25, … , 2( − 1). Banyaknya titik potong dan daerah baru yang dihasilkan masing-masing garis
adalah sebagai berikut.
o Garis 34 tidak memotong garis lain,→daerah baru yang dihasilkan: 1 daerah.
o Garis 35 memotong garis 14 dan 24→daerah baru yang dihasilkan: 3 daerah.
o Garis 36 memotong garis 14 , 15 dan 24 , 25→daerah baru yang dihasilkan: 5 daerah.
o dst
o Garis 3 memotong garis-garis: 14, 15, … , 1( − 1) dan 24, 25, … , 2( − 1); →daerah baru yang
dihasilkan: [2( − 4)+1]daerah.
Banyaknya daerah yang disumbangkan oleh titik 3 adalah: 1 + 3 + 5 + … + [2( − 4)+1]
Sutopo, Fisika UM
5
4
Seri berfikir kombinatorik
2011
Dengan cara yang sama dapat ditunjukkan bahwa:
Banyaknya daerah yang disumbangkan oleh titik ; 1 < ≤ ( − 1) adalah
1 + [1 + ( − 1)] + [1 + 2( − 1)] + [1 + 3( − 1)] + ⋯ + [1 + ( − − 1)( − 1)], yaitu deret
aritmatika dengan = 1, = ( − 1), sebanyak − suku.
Untuk
= 1, banyaknya daerah = 1 + 1 + 1+ … + 1 (sebanyak
suku)
Total banyaknya daerah yang dihasilkan oleh titik pada lingkaran sama dengan jumlahan dari
seluruh daerah yang disumbangkan oleh titik ke 1 s.d ke − 1.
= 10, maka
Contoh, untuk
Titik
ke- =
1
2
3
4
5
6
7
8
9
10
Jum
Deret
1
1
1
1
1
1
1
1
1
0
9
1
2
3
4
5
6
7
8
1
3
5
7
9
11
13
1
4
7
10
13
16
1
5
9
13
17
1
6
11
16
1
7
13
1
8
1
1
36
49
51
45
34
21
9
1
1
= 10
= 36
= 49
= 51
= 45
= 34
= 21
=
9
=
1
=
0
= 256
Karakter
a
b
# suku
1
0
10
1
1
8
1
2
7
1
3
6
1
4
5
1
5
4
1
6
3
1
7
2
1
1
Jika data tersebut ditata dalam bentuk segitiga (dengan memutar 450), diperoleh pola sebagai berikut.
1
2
3
4
5
6
7
8
9
10
11
↑
1
1
1
1
1
1
1
1
1
1
1
↑
+0
1
1
2
3
4
5
6
7
8
9
↑
+1
1
3
5
7
9
11
13
15
↑
+2
1
4
7
10
13
16
19
↑
+3
1
5
9
13
17
21
↑
+4
1
6
11
16
21
↑
+5
1
7
13
19
↑
+6
1
8
15
↑
+7
1
9
↑
+8
1
↑
+9
1=
2=
4=
8=
15 =
26 =
42 =
64 =
93 =
130 =
+
+
+
+
+
+
+
+
+
+
↑
Jum per baris
1
2
4
8
16
31
57
99
163
256
386
↑
( )
( ) dihitung dengan menjumlahkan secara komulatif semua angka pada baris pertama sampai ke .
Sutopo, Fisika UM
6
Seri berfikir kombinatorik
2011
Jika ditata lagi seperti pada segitiga Pascal, diperoleh pola sebagai berikut.
1
1
1
2
1
1
3
1
4
1
5
1
6
1
7
1
8
1
9
1
10
1
11
1
12
1
8
9
10
13
22
↑
n
6
16
26
1
7
13
19
25
15
1
11
21
26
1
9
17
8
5
13
21
25
4
10
16
4
1
7
13
19
1
5
9
2
3
7
11
15
17
3
5
7
2
4
6
1
1
8
15
22
42
64
1
9
17
93
1
130
10
1
176
+
−1
−1
+
adalah ( − 1), yaitu ( ) − ( − 1). Berdasarkan hal
1
3
itu, maka ( ) dapat dihitung dengan menjumlahkan secara komulatif nilai ( − 1) dari = 1 s.d n.
+
=
Tampak bahwa pola tersebut mirip dengan segitiga Pascal. Penyimpangan terhadap segitiga Pascal mulai
nampak pada = 6, seperti yang ditunjukkan pada gambar. POLA BILANGAN APAKAH GERANGAN….?
Selamat menikmati
Catatan:
Tulisan tersebut semata-mata ditulis berdasarkan pemikiran logis, tidak merujuk pada
kaedah/teorema matematika tertentu, karena penulis memang tidak tahu teori-teori itu, jika
memang ada.
Sutopo, Fisika UM
7
Fly UP