Prinsip Sangkar Burung: Dua Peserta Seminar dengan Jumlah Kenalan Sama

Problem

Pada suatu acara seminar matematika dihadiri oleh $n$ orang peserta seminar. Tunjukkan bahwa di antara para peserta seminar tersebut, senantiasa terdapat dua orang peserta seminar yang mempunyai jumlah kenalan sama.
[ON MIPA-PT Matematika 2011, Tingkat Wilayah]

Solusi

Terdapat $n$ orang peserta seminar. Kita tinjau satu orang peserta, sebutlah $x$. Jumlah kenalan yang mungkin dimiliki oleh $x$ adalah anggota dari $\{ 0,1,2,\ldots,n-1 \}$. Dalam hal ini, $0$ jika $x$ tidak punya kenalan dan $n-1$ jika $x$ mengenal semua peserta seminar.

Perhatikan bahwa, kondisi dimana terdapat peserta dengan $0$ kenalan dan peserta lain dengan $n-1$ kenalan, tidak mungkin terjadi secara bersamaan. Dengan kata lain, jika terdapat peserta dengan $0$ kenalan maka pasti tidak ada peserta dengan $n-1$ kenalan. Begitupun sebaliknya.

Kita dapat membuktikan pernyataan tersebut dengan kontradiksi. Asumsikan terdapat peserta $a$ dengan $0$ kenalan dan peserta $b$ dengan $n-1$ kenalan. Karena total peserta adalah $n$, maka $b$ mengenal seluruh peserta lain, termasuk $a$. Akibatnya, $a$ punya sedikitnya $1$ orang kenalan. Terjadi kontradiksi.

Dengan demikian, jumlah kenalan yang mungkin adalah anggota dari $\{ 0,1,2,\ldots,n-2 \}$ atau $\{ 1,2,\ldots,n-1 \}$. Kedua himpunan ini mempunyai kardinalitas yang sama, yaitu $n-1$. Karena terdapat $n$ peserta, maka berdasarkan Prinsip Sangkar Burung, senantiasa terdapat dua orang peserta dengan jumlah kenalan sama. Terbukti.


Bagikan ke:
Click here if solved
Click here to save

Maaf, fitur ini hanya untuk pembaca yang telah terdaftar. Silakan Masuk atau buat akun terlebih dahulu.

Tambah Komentar