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 Batalkan balasan

Artikel Terbaru

Komentar