Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 20–21
Deskripsi Untuk Soal Nomor 20 dan 21
Pak Dengklek mempunyai suatu lantai berukuran N * N petak, yang mana nilai N selalu genap. Terdapat ((N * N / 2) - 1) tegel berukuran 1 x 2 untuk dipasangkan ke lantai tersebut. Pak Dengklek ingin memilih dua petak pada lantai yang tidak akan dipasang tegel untuk dicat dengan warna merah, dan menutupi petak sisanya dengan tegel-tegel tersebut. Berikut adalah beberapa contoh dari pemasangan tegel pada N = 4, dengan banyaknya tegel adalah 7.
Pada ketiga gambar diatas, terdapat 7 tegel yang dinomori dari 1 - 7, dan petak yang tidak dipasang tegel ditandai dengan warna merah. Suatu konfigurasi disebut menarik apabila terdapat minimal satu cara untuk meletakkan seluruh tegel tanpa keluar dari lantai maupun kedua petak berwarna merah. Pada gambar diatas, konfigurasi A, B, maupun C merupakan konfigurasi yang menarik.
Suatu konfigurasi menarik X disebut berbeda dengan suatu konfigurasi menarik Y apabila posisi petak berwarna merah berbeda. Pada gambar diatas, konfigurasi A sama dengan konfigurasi B, akan tetapi konfigurasi C berbeda dengan konfigurasi A maupun B.
20.
Apabila diketahui N = 2, berapa banyak konfigurasi menarik yang berbeda?
Jawaban: ……………. {tuliskan jawaban dalam bentuk angka saja}
21.
Apabila diketahui N = 10, berapa banyak konfigurasi menarik yang berbeda?
Jawaban: ……………. {tuliskan jawaban dalam bentuk angka saja}
3 jawaban
Noya Aldiputera7 tahun lalu
Jika ingin mendownvote, jangan lupa juga untuk komen tentang kesalahannya. That'll be helpful for everyone, don't let that be a habit.
7
Untuk memudahkan peninjauan contoh/visualisasi, saya buat lantai berukuran yang dimana petak-petaknya menyerupai papan catur yang sering Anda lihat. Saya nyatakan sebagai bagian dari observasi, Lemma 1.
Lemma 1. Dua petak merah tidak mungkin berada di paritas yang sama, i.e. selalu berada di warna yang saling berbeda.
Bukti (Parsial). Perhatikan bahwa suatu tegel pasti menempati dua petak dengan warna yang berbeda, sebagaimana dijelaskan dalam figur berikut. Artinya, tegel-tegel ini dapat memenuhi setiap lantai jika banyaknya petak berwarna putih sama dengan banyaknya petak berwarna hitam.
Namun jika dua petak merah berada di paritas yang sama, maka banyaknya petak berwarna putih akan tidak sama dengan banyaknya petak berwarna hitam. Artinya, tegel-tegel ini pun tidak akan berhasil mengisi lantai yang sehingga kita bisa mengambil kesimpulan bahwa dua petak tersebut tidak mungkin berada pada warna yang sama. QED.
Sesuai dari Lemma 1, kita simpulkan juga bahwa banyaknya konfigurasi menarik adalah banyaknya pasangan lokasi dua petak merah yang dimana paritasnya beda. Perhatikan bahwa banyaknya petak berwarna putih atau hitam adalah . Namun untuk setiap petak berwarna putih, kita dapat memasangkan setiap petak ini ke petak yang berwarna hitam sebanyak
cara juga. Dari prinsip perkalian, maka banyaknya konfigurasi yang menarik adalah
. Untuk
dan
masing-masing ada
dan
cara.
Masuk untuk menulis jawaban
