Diberikan 8 bilangan bulat. Tunjukkan bahwa terdapat 2

Menggunakan Prinsip Sangkar Merpati dengan sisa pembagian modulo 12.

Pembahasan

Untuk menunjukkan bahwa dari 8 bilangan bulat, pasti ada 2 bilangan yang jumlah atau selisihnya habis dibagi 12, kita dapat menggunakan Prinsip Sangkar Merpati (Pigeonhole Principle). Kita akan mempertimbangkan sisa pembagian setiap bilangan bulat ketika dibagi dengan 12. Ada 12 kemungkinan sisa pembagian, yaitu 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Kita memiliki 8 bilangan bulat. Kita bisa mengelompokkan sisa pembagian ini menjadi beberapa kategori. Perhatikan pasangan sisa yang jika dijumlahkan atau dikurangkan akan menghasilkan kelipatan 12: (1, 11), (2, 10), (3, 9), (4, 8), (5, 7). Sisa 0 dan 6 adalah kasus khusus. Kita bisa membuat 6 "sangkar": Sangkar 1: {0}, Sangkar 2: {1, 11}, Sangkar 3: {2, 10}, Sangkar 4: {3, 9}, Sangkar 5: {4, 8}, Sangkar 6: {5, 7}, Sangkar 7: {6}. Jika kita memiliki 8 bilangan bulat, menurut Prinsip Sangkar Merpati, setidaknya dua bilangan harus berada dalam sangkar yang sama. Jika dua bilangan berada dalam satu sangkar: - Jika sangkar adalah {0}, kedua bilangan tersebut adalah kelipatan 12, sehingga selisihnya adalah kelipatan 12. - Jika sangkar adalah {6}, kedua bilangan tersebut bersisa 6 ketika dibagi 12. Selisih mereka adalah kelipatan 12 (misal: 6 - 6 = 0, 18 - 6 = 12, dll.). - Jika sangkar adalah {1, 11}, maka bisa jadi kedua bilangan bersisa 1, atau keduanya bersisa 11, atau satu bersisa 1 dan yang lain bersisa 11. Jika keduanya bersisa sama, selisihnya adalah kelipatan 12. Jika satu bersisa 1 dan yang lain bersisa 11, jumlahnya akan bersisa 1+11 = 12, yang merupakan kelipatan 12. Hal yang sama berlaku untuk pasangan (2, 10), (3, 9), (4, 8), (5, 7). Dalam setiap kasus, jika dua bilangan jatuh ke dalam sangkar yang sama, jumlah atau selisih mereka akan habis dibagi 12. Dengan 8 bilangan bulat dan 7 sangkar yang telah ditentukan, pasti ada setidaknya dua bilangan yang jatuh ke dalam sangkar yang sama.