Pembahasan Soal 3 Prinsip Sarang Merpati

Soal: Diberikan himpunan A \subset \{ 1,2,3,4,5,6,7,8,9\} dengan 1\in A dan |A| = 5
1. Buktikkan bahwa pasti ada dua anggota (berbeda) dari A yang jumlahnya habis dibagi 2;
2. Buktikkan bahwa pasti ada dua anggota (berbeda) dari A yang jumlahnya habis dibagi 3;
3. Selidiki apakah pasti ada dua anggota (berbeda) dari A yang jumlahnya habis dibagi 6. Jika tidak, berikan penyangkalnya;
4. Jika diberikan himpunan B \subseteq \{1,2,3,4,5,6,7,8,9\} dengan 1\in B dan |B| = n. Tentukan bilangan terkecil n sehingga pasti ada dua anggota (berbeda) dari B yang jumlahnya habis dibagi 6.

Pembahasan:

1. Diambil sebarang a,b \in A dengan (a+b)\mid 2, maka banyaknya pasangan (a,b) yang memenuhi adalah

    \[\{(1,3),(1,5),(1,7),(1,9),(2,4),(2,6),(2,8),(4,6),\ldots\} .\]

Diperoleh banyaknya pasangan (a,b) adalah 24 pasangan.
Karena 1\in A dan |A| = 5, akan dipilih secara acak 4 anggota sisanya. Berdasarkan ilustrasi ditas pasangan-pasangan yang termuat di A maka dapat disimpulkan pasti ada 2 anggota yang berbeda dari A yang jumlahnya habis dibagi 2.
Keterangan:

  • Jika dari 4 bilangan terpilih ada bilangan ganjil maka akan dipasangkan dengan bilangan ganjil lainnya atau 1.
  • Jika dari 4 bilangan terpilih adalah bilangan genap maka bilangan genap yang berbeda akan berpasangan

2. Diambil sebarang a,b \in A dengan (a+b)\mid 3, maka banyaknya pasangan (a,b) yang memenuhi adalah

    \[\{ (1,2),(1,5),(1,8),(2,4),(2,7),(3,6),(3,9),\ldots\} .\]

Diperoleh banyaknya pasangan (a,b) adalah 24 pasangan. Dari illustrasi diatas, pasti ada dua anggota berbeda dari A yang jumlahnya habis dibagi 3.
Keterangan:

  • Andaikan a \equiv 1 \pmod{3}, maka a akan dipasangkan dengan b \equiv 2 \pmod{3}
  • Andaikan a \equiv 0 \pmod{3}, maka a akan dipasangkan dengan b \equiv 0 \pmod{3}

3. Diambil sebarang a,b \in A dengan (a+b)\mid 6, maka banyaknya pasangan (a,b) yang memenuhi adalah \{ (1,5),(2,4),(3,9),(4,8),(5,7)\}. Dikarenakan terlalu sedikit pasangan yang memenuhi kondisi tersebut, maka besar kemungkinan pasti ada 2 bilangan yang dipilih dari A habis dibagi 6 tidak terpenuhi. Sebagai contoh, jika A dengan anggotanya adalah A = \{1,2,3,6,7\} maka jelas tidak terdapat 2 bilangan berbeda yang dipilih dari A yang habis dibagi 6.

4. Pandang pada jawaban (c) untuk n = 5 tidak memenuhi, akan diselidiki untuk n > 5.
Jika dibentuk B dengan |B| = 6, masih bisa ditemukan bahwa tidak terdapat 2 bilangan berbeda yang habis dibagi 6. Sebagai contoh jika B dengan anggota nya adalah B = \{1,2,3,6,7,8\} maka jelas tidak terdapat 2 bilangan berbeda yang dipilih dari B yang habis dibagi 6. Perhatikan bahwa bilangan yang tersisa yang dipilih dari B diatas adalah \{4,5,9\} dimana jika diambil salah satu dari 3 bilangan tersebut pasti akan ditemukan 2 bilangan berbeda yang dijumlahkan habis dibagi 6. Maka nilai n terkecil adalah \boxed{7}.

Credit: Fadhlan Zhaahiran

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*