Prinsip Sangkar Burung: Bilangan Bulat dengan Semua Digit 1

Problem

Misalkan $n$ merupakan bilangan bulat positif yang tidak habis dibagi oleh 2 dan 5. Perlihatkan bahwa terdapat bilangan bulat $q$ yang merupakan kelipatan dari $n$ sedemikian sehingga semua digit dari $q$ adalah 1. (Contoh: Bila $n=3$, maka $q=111$ adalah kelipatan dari 3 yang semua digitnya adalah 1).
[ON MIPA-PT Matematika 2019, Tingkat Wilayah]

Solusi

Berikut adalah proposisi yang kita gunakan.

Proposisi 1

Misalkan $a,b,c \in \mathbb{Z}$ dengan $a \neq 0$. Jika $a \mid bc$ dan $\text{FPB}(a,b)=1$ maka $a \mid c$.

Misalkan $n$ adalah bilangan bulat positif yang tidak habis dibagi oleh 2 dan 5. Artinya $n$ tidak habis dibagi oleh 10. Dengan kata lain, $\text{FPB}(n,10)=1$ atau $n$ relatif prima dengan 10.

Kita misalkan pula $R(k)$ sebagai bilangan bulat dengan $k$ digit, yang seluruh digitnya adalah 1. Perhatikan $$R(1),R(2),\ldots,R(n+1)$$ yang terdiri dari $n+1$ bilangan. Berdasarkan Algoritma Pembagian, setiap bilangan ini dapat ditulis secara tunggal sebagai $qn+r$, untuk suatu bilangan bulat $q$ dan $r$, dengan $0 \leq r \leq n-1$.

Terdapat $n+1$ bilangan dan $n$ nilai $r$ yang mungkin. Berdasarkan Prinsip Sangkar Burung, terdapat dua bilangan dengan nilai $r$ sama. Misalkan kedua bilangan itu $R(a)$ dan $R(b)$, untuk suatu $a,b \in \{1,2,\ldots,n+1\}$. Tanpa mengurangi perumuman, kita misalkan $a>b$.

Tulis $R(a)=q_1n+r$ dan $R(b)=q_2n+r$, untuk suatu bilangan bulat $q_1$ dan $q_2$. Dengan mengurangkan kedua persamaan, diperoleh $R(a)-R(b)=(q_1-q_2)n$. Akibatnya $n \mid R(a)-R(b)$.

Perhatikan bahwa $R(a)-R(b)$ dapat ditulis sebagai $R(a-b) \cdot 10^b$, sehingga $n \mid R(a-b) \cdot 10^b$. Pada awal pembahasan, kita peroleh $\text{FPB}(n,10)=1$ yang berakibat $\text{FPB}(n,10^b)=1$. Berdasarkan Proposisi 1, diperoleh $n \mid R(a-b)$. Dengan demikian, $R(a-b)$ merupakan kelipatan dari $n$ yang seluruh digitnya adalah 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