Olimpiade Sains Provinsi (OSP) 2015 - Komputer, Nomor 20
Pada kesempatan kali ini, Astrid dan Bonita (nama samaran, bukan nama asli) sedang bosan dan menciptakan sebuah permainan baru. Game nya sangat simple. Mula-mula disediakan N buah batu, lalu pemain secara bergantian mengambil beberapa batu. Pemain yang kehabisan langkah (kehabisan batu) dinyatakan kalah. Namun kali ini aturan permainan ini berbeda. Dalam 1 giliran, pemain hanya boleh mengambil sejumlah tepat 3, 5, 7, atau 9 batu. Karena Astrid lebih tua dari Bonita, Astrid mendapat kesempatan giliran pertama. Apabila mereka berdua mampu bermain secara optimal, berapa banyaknya batu (N) dengan N lebih besar dari 1000, agar Bonita menang di dalam permainan tersebut?
2 jawaban
desya anugrah10 tahun lalu
4
1008
desya anugrah10 tahun lalu
kalo aku sih keliapatan 12 terkecil yang lebih besar dari 1000.
Nadia Maula10 tahun lalu
kenapa pake kelipatan 12?
Muhammad Ayaz Dzulfikar11 tahun lalu
Aku noob
3
Aku gak terlalu ngerti bagian terakhirnya, tapi bisa dijelasin properti sehingga jika permainan dimulai dengan X batu, kita bisa menentukan siapa yang menang
Semisal fungsi F(X) akan mengembalikan true jika pemain yang mendapat giliran dengan sisa X batu dapat menang dalam permainan optimal. Kita bisa mendefinisikan F(X) sebagai berikut :
jika (X < 3) : false // gak bisa ambil langkah lagi
selain itu : (not F(X - 3)) or (not F(X - 5)) or (not F(X - 7)) or (not F(X - 9))
Berikut hasil tabel fungsi F :
| X | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| F(X) | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
dan seterusnya.
Dapat dilihat bahwa fungsi F(X) berpola. Lebih spesifiknya, F(X) == F(X mod 12).
Jika kita ingin Bonita menang, maka permainan harus dimulai dengan X, di mana F(X) bernilai false. Dengan kata lain, Bonita akan menang pada permainan yang dimulai dengan X batu, di mana X mod 12 bernilai 0,1,atau 2
Masuk untuk menulis jawaban
Caranya gimana?