Soal favorit saya lagi: Barisan digit

Soal ini menggunakan solusi yang sangat mirip dengan soal favorit saya yang pernah saya post tahun 2011 dan juga muncul di kontes besar semacam APMO. Mirip. Otomatis jadi soal favorit lagi hehehe. 🙂

Soal. Diberikan barisan digit-digit $2,0,2,9,3,\dots$ sehingga setiap digit merupakan digit terakhir dari hasil jumlah empat digit sebelumnya. Apakah digit-digit $2,0,1,5$ pernah muncul berturutan di dalam barisan tersebut?

Solusi. Misalkan barisannya adalah $(a_n)$ dan didefinisikan dengan $a_n= a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4} \pmod{10}$ dan suku awal $a_0=2,a_1=0,a_2=2,a_3=9$. Perhatikan bahwa banyaknya semua kemungkinan pasangan terurut $(a_{n-4},a_{n-3},a_{n-2},a_{n-1})$ adalah sebanyak $10^4$. Namun, setiap suku di barisan ini didefinisikan dari suatu pasangan teurut demikian dan suatu saat pasangan terurut yang sama akan muncul persis sehingga pastilah suatu saat barisan ini akan periodik (a.k.a. berulang).

Sekarang, definisikan graf berarah $G$ dengan $10^4$ verteks yang merupakan semua kemungkinan pasangan terurut digit $v=(d_1,d_2,d_3,d_4)$, dengan $d_i \in \{0, \dots, 9\}$. Kemudian, akan terdapat edge dari verteks $v=(d_1,d_2,d_3,d_4)$ ke $v'=(d_1',d_2',d_3',d_4')$ jika berlaku
$d_1'=d_2$
$d_2'=d_3$
$d_3'=d_4$
$d_4'=d_1+d_2+d_3+d_4 \pmod{10}$.
yang artinya jika dipandang sebagai barisan pada soal, $v'$ merupakan empat digit berturutan berikutnya setelah empat digit berturutan $v$, dengan melakukan pergeseran satu digit saja.

Perhatikan bahwa graf $G$ merupakan graf berarah sehingga setiap verteks:
(1) pasti memiliki tepat satu out-degree (karena rumus rekursif tersebut),
(2) pasti memiliki tepat satu in-degree (karena empat digit berturutan tersebut diperoleh dari tepat satu kombinasi empat digit berturutan yang memenuhi rekursif juga).
Kedua sifat ini berakibat bahwa graf $G$ merupakan kumpulan disjoint cycles. Jadi, kita ingin memeriksa apa $v=(2,0,2,9)$ dan $w=(2,0,1,5)$ berada pada satu cycle atau tidak. Ini dapat diperiksa dengan melihat bahwa $2,0,1,5$ jika diteruskan akan menjadi $2,0,1,5,8,4,8,5,5,2,0,2,9,\dots$. Dengan demikian, $w=(2,0,1,5)$ memiliki path ke $v=(2,0,2,9)$. Namun, ini berarti $v$ dan $w$ berada pada satu cycle yang sama, sehingga dari $v$ juga akan ke $w$ suatu saat.

Jadi, ya, digit berturutan $2,0,1,5$ akan muncul di dalam barisan digit tersebut.

Refleksi.

Soal ini otomatis menjadi soal favorit saya lagi karena menggunakan sifat graf yang cantik lagi. Soal favorit saya yang lain yang seperti ini adalah soal APMO 2013 yang diambil juga dari jurnal AMM dan sudah pernah saya post sebelumnya di blog saya.

Soal tantangan berikutnya yang mungkin menarik untuk diteliti adalah bagaimana menentukan banyak dan mengkarakterisasi cycle-cycle yang ada pada graf $G$. Apakah ada cara untuk menguji keanggotaan sembarang verteks $v$ di suatu cycle di $G$? Coba dicoret-coret dulu. Hehehe

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s