Argumen Paritas dan Pewarnaan Papan Catur

Paritas mengacu pada sifat keganjilan (oddness) atau kegenapan (evenness) dari suatu bilangan bulat. Dalam banyak masalah eksistensi, kita dapat menunjukkan bahwa suatu konfigurasi tidak mungkin dicapai dengan membuktikan bahwa paritas dari status awal dan status akhir tidak pernah bisa bersesuaian.

1. Aturan Dasar Paritas

Ganjil $\pm$ Ganjil $=$ Genap
Ganjil $\pm$ Genap $=$ Ganjil
Genap $\pm$ Genap $=$ Genap
(Ganjil) $\times$ (Ganjil) $=$ Ganjil
(Ganjil) $\times$ (Genap) $=$ Genap

2. Pewarnaan Papan Catur (Chessboard Coloring)

Banyak masalah paritas yang melibatkan papan catur atau kisi-kisi (grid) dapat diselesaikan dengan memberikan warna hitam dan putih secara berselang-seling sebagai bentuk visual argumen paritas.

Teorema (Pengubinan Papan Catur Terpotong)

Jika sebuah papan catur $8 \times 8$ dihilangkan dua kotak pojoknya yang berlawanan (misal kiri atas dan kanan bawah), maka papan tersebut tidak dapat ditutupi secara sempurna oleh 31 domino berukuran $2 \times 1$ .

Bukti

Setiap domino $2 \times 1$ akan selalu menutupi tepat satu kotak putih dan satu kotak hitam. Dua kotak pojok yang berlawanan memiliki warna yang sama (keduanya putih). Maka papan yang dimodifikasi memiliki 30 kotak putih dan 32 kotak hitam. Karena 31 domino memerlukan 31 kotak putih dan 31 kotak hitam, pengubinan tersebut tidak mungkin dilakukan. $■$

■

Contoh Soal & Pembahasan

Contoh (Invarian Papan Tulis)

Sebuah algoritma dimulai dengan menuliskan bilangan ${1, 2, 3, \dots, 10}$ di papan tulis. Setiap langkah, kita menghapus dua bilangan $a$ dan $b$ , lalu menuliskan $∣ a - b ∣$ sebagai gantinya. Mungkinkah bilangan terakhir yang tersisa adalah 0?

Contoh (Langkah Kuda Catur (Knight Tour))

Dapatkah sebuah kuda catur (knight) melompat dari kotak $a 1$ dan berakhir di kotak $h 8$ dalam tepat 63 langkah dengan mengunjungi setiap kotak di papan catur $8 \times 8$ tepat satu kali?

Latihan Soal

✏️ Latihan Soal 1 (Membalik Gelas)

Tujuh buah gelas diletakkan di atas meja dalam posisi terbalik. Dalam satu langkah, Anda diperbolehkan membalik tepat 2 gelas sekaligus. Mungkinkah semua gelas berakhir dalam posisi tegak?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Awal: 7 terbalik (ganjil). Setiap langkah membalik 2 gelas mengubah jumlah gelas terbalik sebanyak $+ 2, 0,$ atau $- 2$ (paritas invarian). Karena awal ganjil, jumlah gelas terbalik selalu ganjil, sehingga tidak mungkin mencapai 0 gelas terbalik (semua tegak). $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Prinsip Sarang Merpati (Pigeonhole)
Sub-Topik Selanjutnya: Formulasi PIE untuk n Himpunan →

Argumen Paritas dan Pewarnaan Papan Catur

1. Aturan Dasar Paritas

2. Pewarnaan Papan Catur (Chessboard Coloring)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

🏆 Soal ONMIPA Terkait (1 Soal)

Materi Terkait (Linked References) (3)

Formulasi PIE untuk n Himpunan

The Pigeonhole Principle (Prinsip Sarang Merpati)

Naskah Soal & Pembahasan ONMIPA PT 2025 — Seleksi Wilayah

Diskusi & Tanya Jawab

Title