Olimpiade Sains Kota (OSK) 2017 - Komputer, Nomor 10

Cari kpk dari ketiga jumlah tersebut : 7,11,13

7*11*13= e.1001

d. 839

Soal ini mirip dengan soal https://www.kujawab.com/OSKKOM16/10

Kita akan menggunakan CRT (Chinese Remainder Theorem)

Pertama kita misalkan permen Pak Adi MULA-MULA sebagai X. Maka kita akan menemukan persamaan:

X mod 7 = 1

X mod 11 = 8

X mod 13 = 6

Lalu kita ubah persamaan di atas menjadi:

X  1 (mod 7)

X  8 (mod 11)

X  6 (mod 13)

Dari persamaan di atas kita menemukan:

B = 7*11*13 = 1001

dan

b1=7	C1 = 1	B1 = B/b1 =143
b2=11	C2 = 8	B2 = B/b2 = 91
b3=13	C3 = 6	B3 = B/b3 = 77

Lalu kita cari X₁,X₂,X₃ Dengan rumus: B_n * X_n  1 (mod b_n)

B₁ * X₁  1 (mod b₁)

143 * X₁  1 (mod 7)

3 * X₁  15 (mod 7)

X₁ = 5

 

B₂ * X₂  1 (mod b₂)

91 * X₂  1 (mod 11)

3 * X₂  12 (mod 11)

X₁ = 4

 

B₃ * X₃  1 (mod b₃)

77 * X₃  1 (mod 13)

12 * X₃  1 (mod 13)

(-1) * X₃  1 (mod 13)

X₃ = (-1)

 

Setelah mendapatkan semua itu, kita hitung totalnya dengan rumus dari CRT:

X = (X₁*C₁*B₁ + X₂*C₂*B₂ + X₃*C₃*B₃) mod B

X = (5*1*143 + 4*8*91 + (-1)*6*77) mod 1001

X = (715 + 2912 - 462) mod 1001

X = 3165 mod 1001

X = 162

Tapi di sini, X adalah jumlah permen MULA-MULA. Dan karena yang ditanyakan adalah berapa permen yang harus DITAMBAH agar pembagiannya rata, kita cukup mengurangi KPK(7,11,13) yang merupakan jumlah permen total agar rata dengan X yang merupakan perman mula-mula.

= KPK(7,11,13) - X

= 1001 - 162

= 839

 

CMIIW!!

D. 839

Mencari nilai X yang memenuhi dari persamaan tersebut. 

X mod 7 = 1
X mod 11 = 8
X mod 13 = 6

Jika Kita coba A. 331

331 mod 7 = 2 (Jika menggunakan 331 maka lebih 2 dan karena di pernyataan pertama (x mod 7 = 1) maka ditambahkan dengan 2 sehingga menghasilkan 2+1 = 3 )

karena jumlah muridnya 7 maka 3 tidak memenuhi karena seluruh murid harus mendapatkan bagian sama rata.

Sehingga jawaban yang memenuhi adalah D 839 karena jika dimasukan maka akan menghasilkan seperti berikut :

- 839 mod 7 = 6 ( 6 +1 = 7) Memenuhi karena semua akan kebagian 

- 839 mod 11 = 3 (3 + 8  = 11) Memenuhi 

- 839 mod 13 = 7 ( 7 + 6 = 13) Memenuhi 

839 memenuhi karena seluruh murid mendapatkan permen sisa sama rata

Jadi jawaban D. 839

Soal diatas dapat di representasikanL

n mod 7 = 0;

n mod 11 = 0;

n mod 13 = 0;

jadi kita akan cari bilangan terkecil yang habis dibagi oleh ketiga bilangan tersebut.

A. 331 mod 7 = 2 (salah)

B. 543 mod 7  = 4 (salah)

C. 741 mod 7 = 6 (salah)

D. 839 mod 7 = 6 (salah)

E. 1001 mod 7 = 0 (benar), jadi jawabannya E. 1001

sute