Olimpiade Sains Provinsi (OSP) 2013 - Komputer, Nomor 25

Kata kunci untuk soal ini adalah rekursif.

Misalkan saya anggap solusi untuk himpunan {1,2,3,…,a} adalah F(a). Maka jawaban untuk soal ini ada di F(9). Sekarang mari kita analisa fungsi F(a).

Apabila a<1, maka F(a) akan mencari solusi untuk himpunan kosong, berarti F(a) adalah 1 untuk a<1 (hanya ada satu cara, yaitu tidak memilih apapun karena memang tidak ada pilihan).

Bagaimana dengan a>=1? Kita akan mencari solusi untuk himpunan {1,2,3,…,a}. Sekarang kita lihat angka terakhir di himpunan itu (a). Ada dua pilihan, yaitu ambil ke dalam himpunan bagian, atau tidak ambil.

Apabila kita ambil a ke dalam himpunan bagian, maka kita tidak bisa mengambil a-1, dan baru bisa mengambil mulai dari a-2. Sekarang kita perlu mencari F(a-2) apabila kita mengambil a ke dalam himpunan bagian.

Apabila kita tidak ambil a, maka kita bisa mengambil a-1. Sekarang kita perlu mencari F(a-1) apabila kita tidak mengambil a ke dalam himpunan bagian.

Jadi sekarang kita sudah menemukan formula fungsi kita, yaitu:

F(a) = 1, untuk a < 1

F(a) = F(a-1) + F(a-2), untuk a >= 1

Jawaban untuk soal ini adalah F(9). Mari kita hitung:

F(1) = 2

F(2) = 3

F(3) = 5

F(4) = 8

F(5) = 13

F(6) = 21

F(7) = 34

F(8) = 55

F(9) = 89

Jadi jawaban untuk soal ini adalah 89.

berpola sih

untuk 0 anggota =1 (himpunan kosong)

untuk 1 anggota = 1....9 = 9 = 9c1

untuk 2 anggota = 1,3 ... 1,9=7

                            2,4 .... 2,9=6

                             dst

                            7,9 ... 7,9=1

jadi untuk 2 anggota ada 1+2+3+4...+7=28 = 8c2

jadi untuk 3 anggota 7c3 =35

untuk 4 anggota= 6c4 = 15

untuk 5 anggota=5c5 = 1

1+15+35+28+9+1=89