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.

Komentar

15 Februari 2020
pan

keren

Balas
Tambah Komentar