Prinsip Sangkar Burung: Dua Bilangan dengan Selisih Tidak Lebih dari $m-1$

Problem

Perlihatkan bahwa bila $n+1$ bilangan bulat dipilih dari himpunan $\{1,2,\ldots,mn\}$ untuk suatu bilangan bulat $m \geq 2$, maka terdapat dua bilangan bulat yang selisihnya tidak lebih dari $m-1$.
[ON MIPA-PT Matematika 2008, Tingkat Wilayah]

Solusi

Berikut adalah proposisi yang akan kita gunakan

Proposisi 1

Jika $p,q,r,s \in \mathbb{Z}$ dengan $p < q$ dan $r \leq s$ maka $p+r < q+s$

Misalkan $m,n \in \mathbb{Z}$ dengan $m \geq 2$ dan $S=\{1,2, \ldots , mn \}$. Kita partisi himpunan $S$ menjadi $A_i$ untuk $i=1,2,\ldots,n$ dengan $$A_i=\{x \in S \mid (i-1)m < x \leq im \}$$

Kita telah membentuk sebanyak $n$ himpunan. Berdasarkan Prinsip Sangkar Burung, jika kita memilih $n+1$ bilangan bulat dari $S$, maka terdapat dua bilangan yang berasal dari himpunan yang sama. Misalkan himpunan tersebut adalah $A_k$ untuk suatu $k \in \{1,2,\ldots,n\}$ dan kedua bilangan yang dimaksud adalah $a$ dan $b$. Perhatikan bahwa $a,b \in A_k$ berakibat $$\begin{aligned} &(k-1)m < a \leq km \quad &\ldots \ldots (1) \\ &(k-1)m < b \leq km \quad &\ldots \ldots (2) \\ \end{aligned}$$ Gunakan sifat distributif, lalu kalikan setiap ruas pertidaksamaan $(2)$ dengan $-1$, diperoleh $$\begin{aligned} km-m < a \leq km \quad \Rightarrow \quad &km-m < a \text{ dan } a \leq km \\ -km \leq -b < -km+m \quad \Rightarrow \quad &-km \leq -b \text{ dan } -b < -km+m \\ \end{aligned}$$

Dari sini, kita punya $km-m < a$ dan $-km \leq -b$. Berdasarkan Proposisi 1, diperoleh $\textcolor{red}{-m < a-b}$. Selain itu, kita juga punya $a \leq km$ dan $-b < -km+m$. Berdasarkan Proposisi 1, diperoleh $\textcolor{red}{a-b < m}$.

Perhatikan pertidaksamaan yang dicetak dengan warna merah. Dari keduanya, diperoleh $-m < a-b < m$ yang dapat ditulis sebagai $\mid a-b \mid < m$. Karena $a-b$ dan $m$ adalah bilangan bulat, maka bentuk ini sama saja dengan $\mid a-b \mid \leq m-1$. Artinya, selisih dari $a$ dan $b$ tidak lebih dari $m-1$. 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