Pembahasan Soal 2 Prinsip Sarang Merpati

Soal: Diberikan himpunan $A$ yang terdiri atas $20$ bilangan yang diambil dari himpunan $S=\{1,4,7,\ldots,100\}$ . Buktikkan bahwa setidaknya ada $2$ bilangan yang dipilih dari $A$ berjumlah $104$ .

Pembahasan:

Dengan melihat pola dari himpunan $S$ , jelas bahwa $S$ membentuk barisan $a_{n}=3n-2,\forall n \in \{1,2,3,\ldots,34\}$ . Jika $a_{i}$ dan $a_{j}$ adalah dua buah bilangan yang dipilih dari $S$ yang memiliki jumlah $104$ , maka diperoleh

$3i-2+3j-2=140 \iff i+j=36 .$

Artinya, pernyataan pada soal akan ekuivalen dengan menunjukkan terdapat $20$ bilangan yang dipilih dari $\{1,2,3,\ldots,34\}$ maka ada $2$ bilangan yang jumlahnya $36$ .

Selanjutnya, akan ditunjukkan jika $20$ bilangan yang dipilih dari $\{1,2,3,\ldots,34\}$ maka ada $2$ bilangan yang jumlahnya $36$ . Pasangan bilangan yang jumlahnya $36$ , yaitu

$\{2,34\},\{3,31\},\ldots,\{17,19\}.$

Didapat, ada $16$ pasang bilangan yang setiap pasangannya berjumlah $36$ . Artinya, dari $20$ bilangan yang dipilih pasti ada dua bilangan yang berpasangan memiliki jumlah $36$ .

Dengan demikian, terbukti bahwa himpunan $A$ terdiri ada $20$ bilangan yang diambil dari himpunan $S=\{1,4,7,\ldots,100\}$ , maka setidaknya ada $2$ bilangan yang dipilih dari $A$ berjumlah $104$ .

Credit: Fadhlan Zhaahiran

Leave A Comment Batalkan balasan

Artikel Terbaru

Komentar