[Belgia Junior 2004] Kita mulai dari bilangan 11. Setiap langkah, Anda boleh mengali 2 atau mengurangi 3. Berapa langkah minimal agar hasilnya 25?
Solusi
Kita dapat balik langkahnya, yaitu dari 25, setiap langkah dibagi 2 atau ditambah 3. Misalkan dibagi 2 dinyatakan A, ditambah 3 dinyatakan B. Ini dapat dilakukan dalam 7 langkah (BAABABB). Kita perlu buktikan bahwa ini tidak mungkin dalam 6 langkah atau kurang.
Awalnya 25 adalah 1 (mod 3), sedangkan 11 adalah 2 (mod 3). Ini menyebabkan banyaknya langkah A adalah bilangan ganjil, yaitu 1, 3, atau 5.
1 tentunya tidak mungkin, karena hasil akhirnya pasti kurang dari 11.
Jika 5 langkah A, kita hanya punya 1 langkah B. Ini pasti di awal, karena 25 tidak habis dibagi 2. Tetapi BAAAAA tidak menghasilkan 11.
Anggap 3 langkah A, 3 langkah B. Awalnya adalah B, menghasilkan 28. Kalau bilangannya genap, kita tidak boleh melangkah B, karena menyebabkan harus melangkah B lagi (karena ganjil), dan tidak memenuhi lagi. Maka susunannya harus BAABAB, tetapi ini tidak menghasilkan 11.
Jadi tidak ada susunan kurang dari 7 langkah. Langkah minimalnya adalah 7.
