Bagi siswa/siswi SMA yang ikut seleksi babak penyisihan OMITS minggu kemarin pasti tahu maksud dari judul di atas. Ya, posting kali ini memang terinspirasi dari soal nomor satu penyisihan OMITS 2015. Bagi yang tidak tahu ini soalnya
Saya pribadi berpendapat bahwa soal ini lumayan sadis. Bukan hanya karena tergolong susah, akan tetapi posisinya yang ada di nomor satu dengan tingkat kesulitan tinggi yang membuatnya jadi perhatiannya. Karena kalau hanya menggunakan parameter susah saja maka masih banyak soal lain yang jauh lebih sadis.Lalu bagaimana cara menyelesaikan soal di atas? Jika Anda juga penasaran, mari kita bahas bersama. Namun, saya minta maaf sebelumnya, karena penyelesaian yang akan saya sampaikan cukup panjang dan jauh dari kata elegan.
Untuk memulai menjawab soal ini terlebih dahulu kita cari banyaknya digit $0$(nol) pada bagian akhir bilangan $2015!$. Tentunya bukan hal yang susah. Ini sudah tergolong mainstream. Banyaknya digit $0$ ada\begin{equation*}
\left\lfloor\frac{2015}{5}\right\rfloor+\left\lfloor\frac{2015}{5^2}\right\rfloor+\left\lfloor\frac{2015}{5^3}\right\rfloor+\left\lfloor\frac{2015}{5^4}\right\rfloor=403+80+16+3=502
\end{equation*}
Selanjutnya misalkan $N=\dfrac{2015!}{10^{502}}$. Maka pertanyaan pada soal meminta kita untuk mencari nilai dari $N\text{ mod }1000$. Agar pekerjaan lebih mudah, untuk mencari nilai dari $N\text{ mod }1000$ dapat kita pecah terlebih dahulu menjadi dua kasus yaitu mencari $N\text{ mod }8$ dan $N\text{ mod }125$.
Untuk kasus mencari nilai dari $N\text{ mod }8$ bukan hal yang sulit sebab $N$ habis dibagi $8$. Oleh karena itu, $N\equiv 0\text{ mod }8$. Bagian tersulitnya adalah mencari nilai dari $N\text{ mod }125$. Untuk keperluan ini, terlebih dahulu perhatikan hal berikut : untuk sebarang bilangan asli $k$ maka
\begin{align*}
(5k+1)(5k+2)(5k+3)(5k+4)&=(25k^2+25+4)(25k^2+25+6)\\
&=625(k^2+k)^2+250(k^2+k)+24\\
&\equiv 24\text{ mod }125
\end{align*}
Kemudian misalkan $T=\dfrac{2015!}{5^{502}}$. Kelompokkan perkalian bilangan pada $T$ menjadi empat-empat dan gunakan fakta yang kita miliki di atas. Sebagai ilustrasi saya berikan contoh cara pengelompokan untuk bilangan yang lebih kecil. Semoga dengan demikian akan lebih mudah dimengerti
\begin{align*}
\frac{20!}{5^4}&=(1\cdot2\cdot3\cdot4)\cdot1\cdot(6\cdot7\cdot8\cdot9)\cdot2\cdot(11\cdot12\cdot13\cdot14)\cdot3\cdot(16\cdot17\cdot18\cdot19)\cdot4\\
&\equiv 24\cdot24\cdot24\cdot24\cdot24\text{ mod }125
\end{align*}
Nah, akhirnya dengan cara pengelompokan yang sama akan kita dapatkan
\begin{align*}
T&\equiv 24^{502}\cdot1\cdot2\cdot3\cdot16\cdot401\cdot402\cdot403\text{ mod }125\\
&\equiv 24^{502}\cdot(-24)\text{ mod }125\\
&\equiv -(24)^{503}\text{ mod }125
\end{align*}
Namun dari Teorema Euler kita peroleh $24^{100}\equiv 1\text{ mod }125$. Akibatnya
\begin{equation*}
T\equiv-24^3\equiv 51\text{ mod }125
\end{equation*}
Perhatikan juga bahwa $2^{502}\equiv 4\text{ mod }125$. Dari sini kita peroleh
\begin{align*}
N&=\frac{T}{2^{502}}\\
&\equiv\frac{51}{4}\text{ mod }125\\
&\equiv\frac{176}{4}\text{ mod }125\\
&\equiv 44\text{ mod }125
\end{align*}
Akhirnya ketemu juga, $N\equiv44\text{ mod }125$.
Pada akhirnya kita memiliki dua persamaan kongruensi yaitu
\begin{align*}
N&\equiv0\text{ mod }8\\
N&\equiv44\text{ mod }125
\end{align*}
Dan untuk mencari solusinya tidaklah susah. Misalkan $N=8k$, diperoleh
\begin{align*}
8k&\equiv44\text{ mod }125\\
2k&\equiv11\text{ mod }125\\
k&\equiv68\text{ mod }125
\end{align*}
dengan kata lain $k=125m+68$ sehingga $N=8(125m+68)=1000m+544$.
Huftt, akhirnya dapat juga $N\equiv544\text{ mod }1000$, dan problem kita telah terpecahkan.
ndak ada metode yang lebih ringkas kah?
agak pusing saya memahaminya!
Monggo dicari cara yang lebih ringkas
maksudnya?
Maksudnya, jika ada yang menemukan cara lain yang lebih ringkas, mari dibagikan (saya juga mau tahu, hehehe)
Saya bingung di
T ≡ (25^502)⋅1⋅2⋅3⋅16⋅401⋅402⋅403 mod 125
bukankah seharusnya
T ≡ (24^502)⋅1⋅2⋅3⋅16⋅401⋅402⋅403 mod 125
Hehehe, itu typo saja pas nulis. Terimakasih atas koreksinya. Sudah saya betulkan
Saya maaih tetap bingung disitu, kalau penjelasan lainnya sudah oke. Saya ketemunya (24^503).5.401.402.403mod125… Kesalahan saya apa ya, saya pakai jika pakai kelipatan 20, karena setiap kelipatan 20 ada 24^5, jadi hasilnya (24^503).2005.2010.2015:5² jadi ya kembali ke awal… Letak kesalahannya dimana ya, atau saya salah ambil bilangan 4 perkalian bil berurutan?
Lalu jawaban Nya yang mana????
Saya bener-bener bingung, kalau bisa lebih ringkas ya.. Tolong di betul kan, singkat,padat,jelas,sederhana kan lebih baik, ya ga.. ^______^
Saya bingung dengan pertanyaan Anda. Bukankah jawabannya sudah jelas?
Kalau yang lebih ringkas? Maaf saya belum tahu
Pembahasan yang menarik. \(\frac\{2015!}{5^{502}}\)
Sy ada penyelsaian yang lain, tp ga paham cara nulisnya di blog ini. Saya ketik pake latex. Bisa dicek di sini (https://brilliant.org/problems/last-three-digit-non-zero/#)
Yes, thanks for your sharing.
But i think the idea behind both of this soluition is similar
Saluut dan Jaya terus buat blog http://tuturwidodo.com !
Penjelasannya sangat bagus..
Btw, saya mau request ne mas !
Modul atau buku² panduan tentang Olimpiade Matematika mas..
Karena, saya juga pengen belajar Matematika seperti mas Widodo !!
^_^
Harap di Reply ya mas..!!!
Terimakasih atas doanya,
Untuk buku dan modul sih ada niat, tapi ngelanjutin niatnya itu yang susah
hehehe..
Thank you mas..
Saya harap, mas Widodo tetap semangat dalam mengembangkan dan memajukan ilmu matematika di dunia ini khususnya Republik Indonesia.
Tapi, apabila sudah menyelesaikan modul, diktat atau note tentang Olimpiade Matematika nya, harap di share ya mas…
Bravo Tutur Widodo !
ijin share dan sedot ilmunya semoga berkah dan bermanfaat ya Mas Tutur Widodo. mantap dan keren abiz,Tetap semangat berkarya dan berbagi.
Maaf mas Tutur, saya masih bingung kenapa 2k mod 125 = 11 , lalu tiba-tiba k mod 125 = 68. Saya masih baru dalam hal ini. Mohon dijelaskan mas. Thx 🙂
Malam mas, saya masih agak bingung dengan N mod 1000 dibagi menjadi 2 yaitu N mod 8 dan N mod 125.
N mod 8 =0 dapat darimana ya mas? Bagaimana memastikan nilai N=2015!/10^502 habis dibagi 8?
Pak tutur widodo,ini Ndak pak tutur yang kabupaten solo itu ???
Tolong di reply pak
Semoga Allah memberikan keberkahan kepada keluarga mas