Sign in to follow this  
donjar

Bilangan tawas

Recommended Posts

Sebut sebuah bilangan asli tawas bila setiap dua digit yang bersebelahan di representasi desimalnya berbeda paritas. Contohnya, 1, 12 dan 123454327 merupakan bilangan-bilangan tawas. Diberikan $n$ bilangan asli. Buktikan bahwa semua kelipatan dari $n$ tidak tawas jika dan hanya jika $n$ habis dibagi 20.

 

Sumber:

IMO Shortlist 2004 N5

Share this post


Link to post
Share on other sites
Spoiler

Jika $n$ habis dibagi $20$ jelas dua digit terakhir dari kelipatan $n$ selalu keduanya genap, maka semua kelipatan dari $n$ tidak tawas. Sekarang akan ditunjukkan kalau ada kelipatan $n$ yang tawas jika $n$ tidak habis dibagi $20$.

 

Jika $4$ tidak habis membagi $n$, maka ada empat kemungkinan, $n=2.5^t.m$ atau $n=5^t.m$ atau $n=2^t.m$ atau $n=m$ dengan $(m,10)=1$, dan $t$ positive integer.

 

Akan dibuktikan untuk $m=1$ ada kelipatan dari $n$ yang tawas. \vspace{3mm}

 

Kasus 1: $n=5^t$

 

Akan diselesaikan dengan induksi di $t$, akan ditunjukkan kalau ada bilangan $t$ digit yang tawas dan habis dibagi $5^t$. Jelas untuk $t=1$ ada (5).

 

Misalkan untuk $t=k+1$ ada . Berarti ada $a_0,a_1,...,a_k\in \{0,1,2,...,9\}$ sehingga $5^{k+1}|\sum\limits_{i=0}^k a_i.10^i$ (ini mengobservasi $k+1$ digit, karena tawas berarti alternating paritasnya). Maka $\sum\limits_{i=0}^k a_i.10^i\equiv n.5^{k+1} (mod 5^{k+2})$, dengan $0\le n\le 4$. Perhatikan kalau $\sum\limits_{i=0}^k a_i.10^i + (5-n).10^{k+1}$ dan $\sum\limits_{i=0}^k a_i.10^i + (10-n).10^{k+1}$ keduanya habis dibagi $5^{k+2}$, dan representasi digitnya dalam basis $10$ itu $k+1$ digit, lalu karena digit paling kiri bisa $5-n$ atau $10-n$ (yang paritasnya beda), bisa dipilih sehingga paritasnya alternating, hence tawas. Induksi selesai.\vspace{3mm}

 

Kasus 2: $n=2.5^t$

 

Akan diselesaikan dengan induksi di $t$, akan ditunjukkan kalau ada bilangan $t$ digit yang tawas dan habis dibagi $2.5^t$ untuk $t\ge 2$. Jelas untuk $t=2$ ada (50). Untuk $t=1$ jelas 10 memenuhi. Perhatikan kalau hanya perlu di observe apakah bilangan itu habis dibagi $5^t$ dan genap (yangn hanya concerned sama digit terakhir)

 

Misalkan untuk $t=k+1$ ada . Berarti ada $a_0,a_1,...,a_k\in \{0,1,2,...,9\}$ sehingga $5^{k+1}|\sum\limits_{i=0}^k a_i.10^i$ (ini mengobservasi $k+1$ digit, karena tawas berarti alternating paritasnya, dan karena habis dibagi 2 berarti digit paling kanan genap). Maka $\sum\limits_{i=0}^k a_i.10^i\equiv n.5^{k+1} (mod 5^{k+2})$, dengan $0\le n\le 4$. Perhatikan kalau $\sum\limits_{i=0}^k a_i.10^i + (5-n).10^{k+1}$ dan $\sum\limits_{i=0}^k a_i.10^i + (10-n).10^{k+1}$ keduanya habis dibagi $5^{k+2}$, dan representasi digitnya dalam basis $10$ itu $k+1$ digit, lalu karena digit paling kiri bisa $5-n$ atau $10-n$ (yang paritasnya beda), bisa dipilih sehingga paritasnya alternating, hence tawas. Induksi selesai.\vspace{3mm}

 

Kasus 3: $n=2^t$

 

Akan dibuktikan dengan induksi di $t$ kalau ada kelipatan $n$ yang tawas dan hanya $t$ digit. Jelas ini benar untuk $t=1,2,3,4$ (2, 32, 632, 1632)

 

Misalkan ini benar untuk $t\le 2k$, $k\ge 2$.

 

Perhatikan kalau untuk $t=2k+1$, kita ingin $a_0,a_1,...,a_{2k}\in \{0,1,2,...,9\}$ sehingga $2^{2k+1}|\sum\limits_{i=0}^{2k} a_i.10^i$. Menurut induksi ada $a_0,a_1,...,a_{2k-1}\in \{0,1,2,...,9\}$ sehingga $2^{2k-1}|\sum\limits_{i=0}^{2k-1} a_i.10^i$, dengan paritas $a_i$ alternating (bilangannya tawas). Perhatikan kalau haruslah $a_0$ genap, maka agar bilangannya tawas kita ingin $a_i$ paritasnya sama dengan paritas $i$. Maka mudah dilihat kalau $2^{2k-1}|a_{2k-1}.10^{2k-1}+a_{2k-2}.10^{2k-2}$, maka ada $a_0,a_1,...,a_{2k-3}\in \{0,1,2,...,9\}$ sehingga $2^{2k-1}|\sum\limits_{i=0}^{2k-3} a_i.10^i$, dengan paritas $a_i$ alternating (bilangannya tawas). Ambil $2k-3$ bilangan ini untuk kasus yang sedang kita kerjakan, lalu jelas yang ingin dicari ekuivalen dengan $4|a_{2k}.2.5^{2k}+a_{2k-1}.5^{2k-1}+\frac{a_{2k-2}}{2}.5^{2k-2}+h$ untuk suatu $h\in \mathbb{N}$. Jelas $\frac{a_{2k-2}}{2}$ bisa kongruen berapapun modulo 4, maka ada solusi.

 

Untuk $t=2k+2$, perhatikan kalau yang ingin dicari adalah $2^{2k+2}| \sum\limits_{i=0}^{2k+1} a_i.10^i$. Karena $a_2k+1$ odd, kita ingin $2^{2k+2}\nmid \sum\limits_{i=0}^{2k} a_i.10^i$. Namun $a_{2k}.10^{2k}$ bisa diatur menjadi habis dibagi $2^{2k+2}$ atau tidak (pilihnya $a_{2k}=2$ kalau gamau habis dibagi, otherwise $a_{2k}=4$). Jadi bisa dipilih sehingga $2^{2k+2}| \sum\limits_{i=0}^{2k+1} a_i.10^i$ dengan $a_{2k+1}$ odd.

 

Kasus 4: $n=1$

 

Jelas lah ya

 

Perhatikan kalau untuk kasus 1, kasus 2, kasus 3 konstruksi yang digitnya ada ganjil buah bisa ditambahin digit selanjutnya (yang penting genap) dan tetap kelipatan $n$. Untuk kasus 4 jelas lah ya

 

Jadi untuk setiap $n$ diatas bisa dikonstruksi bilangan genap digit yang kelipatan $n$ dan tawas. Misalkan kelipatannya adalah $K$ dan banyaknya digit adalah $H$. Perhatikan kalau $\sum\limits_{i=0}^{j} K.10^{i.H}$ juga tawas dan kelipatan $n$. Lalu $\sum\limits_{i=0}^{j} K.10^{i.H}=K\frac{10^{(j+1)H}-1}{10^H-1}$,

 

Perhatikan kalau ada dipilih $j$ sehingga order $m$ dari $10$ habis membagi $j+1$, maka $m|10^{(j+1)H}-1$, lalu karena untuk setiap $p$ prima yang membagi $m$ menurut lifting the exponent $V_p(10^{(j+1)H.l}-1=V_p(10^{(j+1)H}-1)+V_p(l)$, maka bisa dipilih $j$ sehingga $V_p(10^{(j+1)H}-1)$ arbitrarily large. Dengan cara yang sama bisa dibuat sehingga $V_p(10^{(j+1)H}-1)$ arbitrarily large untuk semua $p$ prima yang membagi $m$ secara simultaneous. Maka jelas untuk setiap $m$ relatif prima dengan $10$ ada $j$ sehingga $m|\frac{10^{(j+1)H}-1}{10^H-1}$.

 

Jelas semua bilangan berbentuk $\frac{10^{(j+1)H}-1}{10^H-1}$ tawas dan untuk setiap $m$ relatif prima 10 bisa dipilih $j$ sehingga $m|\frac{10^{(j+1)H}-1}{10^H-1}$, maka jika $t$ ada kelipatannya yang tawas, $tm$ ada kelipatannya yang tawas untuk $m$ relatif prima dengan 10.

 

Jadi untuk setiap $n$ yang tidak habis dibagi $20$, ada kelipatan $n$ yang tawas. Maka semua kelipatan $n$ tidak tawas jika dan hanya jika $n$ habis dibagi 20.

 

 

Share this post


Link to post
Share on other sites

Ini yang saya kepikiran cuman, semua bilangan ganjil yang tidak habis dibagi 5, punya kelipatan berbentuk 1010101...01... Kalau habis dibagi 5 tinggal kali 2 kemudian bisa jadi 101010101...10.

 

Nah kalau bilangan genap entah deh :v

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this