Pembahasan Soal 4 Prinsip Sarang Merpati

Soal: Diberikan himpunan

    \[\displaystyle A = \Big\{a_{n}|a_{n} = \binom{2021}{n},n=0,1,2,\ldots,1010\Big\}.\]

Buktikkan bahwa ada sedikitnya 253 anggota A yang mempunyai sisa yang sama ketika dibagi 4.

Pembahasan:

Misal A_{i} adalah himpunan yang berisikan bilangan yang bersisa i jika dibagi 4, dengan A_{i} \subseteq A, \forall i = 0,1,2,3.
Katakan A sebagai kumpulan merpati dengan |A|=1010 dan A_{i} sebagai sangkar. Maka berdasarkan prinsip sarang burung, satu sangkar paling sedikit berisi \lceil \frac{1010}{4}\rceil = 253 merpati.

Jadi, terbukti bahwa setidaknya ada 253 anggota A yang mempunyai sisa yang sama ketika dibagi 4.

 

Credit: Fadhlan Zhaahiran

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*