SOAL LATIHAN OLIMPIADE MADRASAH INDONESIA (OMI) DAN ALTERNATIF PENYELESAIANNYA (PART A)

Given a positif integer n, let p(n) be the product of the non-zero digits of n. (if n has only one digit, then p(n) is equal to that digit).

Let S = p(1) + p(2) + ... + p(999).

What is the largest prime factor of S?

Terjemahan soal dalam bahasa Indonesia:

Diberikan sebuah bilangan bulat positif n, misalkan p(n) adalah hasil perkalian digit-digit bukan nol dari n. (jika n hanya memiliki satu digit, maka p(n) sama dengan digit tersebut).

Misalkan S = p(1) + p(2) + ⋯ + p(999).

Berapakah faktor prima terbesar dari S?

ALTERNATIF PENYELESAIAN

Analisis Soal

Soal tersebut meminta kita untuk menemukan faktor prima terbesar dari S, di mana S = p(1) + p(2) + ⋯ + p(999).

Fungsi p(n) didefinisikan sebagai hasil perkalian digit-digit bukan nol dari bilangan bulat positif n. 

Jika n hanya memiliki satu digit, maka p(n) adalah digit itu sendiri.

Contoh

• p(123) = 1 × 2 × 3 =6

• p(405) = 4 × 5 = 20

• p(7) = 7

Soal tersebut menguji pemahaman tentang konsep perkalian digit dan penjumlahan seri.

Kita bisa memecah penjumlahan S menjadi tiga bagian:

1. Penjumlahan untuk bilangan 1 hingga 9 (p(1) + p(2) + ⋯ + p(9))

2. Penjumlahan untuk bilangan 10 hingga 99 (p(10) + p(11) + ⋯ + p(99))

3. Penjumlahan untuk bilangan 100 hingga 999 (p(100) + p(101) + ⋯ + p(999))

1. Penjumlahan untuk bilangan 1-digit (1 hingga 9)

Untuk bilangan 1-digit, p(n) sama dengan n.

Jumlahnya adalah 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9.

Jumlah tersebut dapat dihitung dengan rumus jumlah deret aritmatika: = (9 : 2)(1 + 9)

= (9 : 2) × 10

= 9 × 5

= 45

2. Penjumlahan untuk bilangan 2-digit (10 hingga 99)

Setiap bilangan 2-digit dapat ditulis dalam bentuk 10a + b, di mana a adalah digit puluhan (1 ≤ a ≤ 9) dan b adalah digit satuan (0 ≤ b ≤ 9). 

p(10a + b) = a × b jika b ≠ 0,

dan

p(10a) = a.

Mari kita hitung jumlahnya berdasarkan digit puluhan dan satuan.

• Untuk bilangan 2-digit secara umum

Kita dapat menghitungnya dengan menjumlahkan semua perkalian a × b untuk a ∈ {1, …, 9} dan b ∈ {1, …, 9}, dan menambahkan nilai p(n) untuk bilangan dengan digit satuan 0.

p(10) =1, p(20) =2, …, p(90) = 9

Jumlahnya adalah 1 + 2 + ... + 9 = 45.

p(11) + p(12) + ... + p(19) = 1 × (1 + 2 + ... + 9) = 1 × 45

p(21) + p(22) + ... + p(29) = 2 × (1 + 2 + ... + 9) = 2 × 45

p(31) + p(32) + ... + p(39) = 3 × (1 + 2 + ... + 9) = 3 × 45

...

p(91) + p(92) + ... + p(99) = 9 × (1 + 2 + ... + 9) = 9 × 45

Total jumlah untuk bilangan 2-digit

Jumlah untuk digit satuan 0 = 45

Jumlah untuk digit satuan 1 - 9

= (1 + 2 + ... + 9) × (1 + 2 + ... + 9)

= 45 × 45

= 2025

Total jumlah untuk 2-digit

= 45 + 2025

= 2070

3. Penjumlahan untuk bilangan 3-digit (100 hingga 999)

Setiap bilangan 3-digit dapat ditulis sebagai 100a + 10b + c, di mana a ∈ {1, …, 9}, b ∈{0, …, 9}, dan c ∈ {0, …, 9}.

• Jumlah untuk p(abc) di mana a, b, c ≠ 0

a ∈ {1, …, 9}, b ∈ {1, …, 9}, c ∈ {1, …, 9}

Totalnya

 = 45 × 45 × 45

= 91125

• Jumlah untuk p(ab0) di mana a,b ≠ 0

a ∈ {1, …, 9}, b ∈ {1, …, 9}

Totalnya

= 45 × 45

= 2025

• Jumlah untuk p(a0c) di mana a, c ≠ 0

a ∈ {1, …, 9}, c ∈ {1, …, 9}

Totalnya

= 45 × 45

= 2025

• Jumlah untuk p(a00) di mana a ≠ 0

a ∈ {1, …, 9}

Totalnya = 45

Total jumlah untuk bilangan3-digit

= 91125 + 2025 + 2025 + 45

= 95220

Total S

= 45 + 2070 + 95220

= 97335

Sekarang kita perlu mencari faktor prima terbesar dari 97335.

• 97335 dapat dibagi 5 karena berakhiran 5

97335 : 5

= 19467

• Jumlah digit 19467 adalah 1 + 9 + 4 + 6 + 7 = 27, yang habis dibagi 9 dan 3.

19467 : 9 = 2163

• Jumlah digit 2163 adalah 2 + 1 + 6 + 3 = 12, yang habis dibagi 3.

2163 : 3= 721

• Sekarang kita punya bilangan 721.

721 : 7 = 103

• 103 adalah bilangan prima.

• Faktorisasi prima dari 97335

= 5 × 9 × 3 × 7 × 103

= 3³ × 5 × 7 × 103

Faktor-faktor prima dari S = 97335 adalah 3, 5, 7, dan 103.

Jadi, faktor prima terbesar dari S adalah 103.