Prinsip Sangkar Burung: Beberapa Suku Berurutan yang Jumlahnya Habis dibagi $m$

Problem

Buktikan bahwa dalam sebarang barisan yang terdiri dari $m$ bilangan bulat terdapat satu atau beberapa suku berurutan yang jumlahnya habis dibagi $m$.
[ON MIPA-PT Matematika 2010, Tingkat Wilayah]

Solusi

Berikut adalah proposisi yang akan kita gunakan

Proposisi 1

Misalkan $p \in \mathbb{N}$. Setiap bilangan bulat kongruen modulo $p$ dengan tepat satu anggota dari $\{0,1,\ldots,p-1\}$.

Proposisi 2

Misalkan $p \in \mathbb{N}$ dan $w,x,y,z \in \mathbb{Z}$. Jika $w \equiv x \pmod{p}$ dan $y \equiv z \pmod{p}$ maka $w-y \equiv x-z \pmod{p}$.

Misalkan $A:=\left( a_1,a_2,\ldots,a_m \right)$ adalah barisan bilangan bulat. Kita bentuk barisan $B:= \left( b_1,b_2,\ldots,b_m \right)$ dengan $$b_i = a_1+a_2+\ldots+a_i, \quad \text{untuk } i=1,2,\ldots,m$$ Jika $B$ mempunyai suku yang habis dibagi $m$, sebutlah $B_z$, maka kita telah menemukan beberapa suku berurutan dari $A$ yang jumlahnya habis dibagi $m$, yaitu $$a_1,a_2, \ldots, a_z$$ Terbukti. Namun, bagaimana jika $B$ tidak mempunyai suku yang habis dibagi $m$? Nah, sesuai judul, kita menggunakan Prinsip Sangkar Burung. Berdasarkan Proposisi 1, setiap suku dari $B$ kongruen modulo $m$ dengan tepat satu dari $\{0,1,\ldots,m-1\}$. Namun, tidak ada suku dari $B$ yang habis dibagi $m$, sehingga yang tersisa adalah $\{1,2,\ldots,m-1\}$. Untuk $j=1,2,\ldots,m-1$, kita bentuk himpunan $H_j$ yang berisi suku-suku dari $B$ yang kongruen modulo $m$ dengan $j$.

Terdapat $m-1$ himpunan dan barisan $B$ terdiri dari $m$ suku. Berdasarkan Prinsip Sangkar Burung, terdapat dua suku yang berasal dari himpunan yang sama, sebutlah $H_k$ untuk suatu $k \in \{1,\ldots,m-1\}$. Misalkan $b_x$ dan $b_y$ adalah dua anggota $H_k$ yang dimaksud, sehingga $b_x \equiv k \pmod{m}$ dan $b_y \equiv k \pmod{m}$. Tanpa mengurangi perumuman, kita asumsikan $x>y$. Berdasarkan Proposisi 2, diperoleh $b_x-b_y \equiv 0 \pmod{m}$. Artinya $m \mid b_x-b_y$.

Karena $x>y$, maka $$\begin{aligned} b_x &= \textcolor{red}{a_1+a_2+\ldots+a_y}+a_{y+1}+a_{y+2}+\ldots+a_x \\ b_x &= \textcolor{red}{b_y}+a_{y+1}+a_{y+2}+\ldots+a_x \\ b_x-b_y &= a_{y+1}+a_{y+2}+\ldots+a_x \end{aligned}$$ Dengan demikian, $m$ habis membagi $a_{y+1}+a_{y+2}+\ldots+a_x$ yang merupakan jumlah beberapa suku berurutan dari $A$. 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