Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 2

INGAT : A xor B =TRUE jika nilai A dan B tidak sama

Misalkan semua kalimat bernial TRUE

Maka berakibat

X2=X1 (dalam bool) ......kalimat 1

X5=X6 (dalam bool)......kalimat 2

X5!=X4 (dalam bool)......kalimat 3

X3!=X4 (dalam bool)......kalimat 4

X3=X5 (dalam bool)......kalimat 5

X7=X8 (dalam bool)......kalimat 6

X9=X9 (dalam bool)......kalimat 7

X6!=X3(dalam bool)......kalimat 8

Perhatikan kalimat 2,5,8

dari kalimat 2 dan 5 didapat bahwa X3=X6 (dalam bool)

Namun pada kalimat 8 didapat bahwa X6!=X3 (dalam bool)

Kontradiksi

Berarti Pemisalan "Misalkan semua kalimat bernilai true" salah , negasi nya adalah pasti ada 1 kalimat yang bernilai false

Berarti bagaimanapun konfigurasinya pasti ada 1 kalimat yang bernilai false, sedangkan untuk membentuk konfigurasi dari X1 sampai X9 ada 2^9=512 cara karena X1 bisa true/false begitu seterusnya hingga X9

Jadi jawabannya 512

 

Kita konstruksikan kalimat-kalimat boolean ini dalam suatu graf yang dimana

• jika untuk suatu  dan , , maka kita labeli edge dari verteks ke- sampai ke- dengan warna merah, dan
• selain itu warna biru.

Alhasil kita dapatkan graf berikut ini. Perhatikan bahwa  = 1,  = 2, dan seterusnya.

Observasi 1. Subgraf pada verteks 9 selalu true untuk setiap nilai kebenaran .

Observasi 2. Terdapat  kemungkinan dalam mengeset subgraf A-B-G-H-I sedemikian sehingga semua edgenya menjadi true. Terdapat 2⁵ kemungkinan untuk tupel (A, B, G, H, I) atau nilai kebenaran "verteks-verteks" tersebut.

Observasi 3. Lihatlah pada subgraf yang berbentuk jajar genjang. Sekarang masalah kita tersimplifikasi menjadi bagaimana kita mewarnai verteks-verteks pada subgraf ini dengan dua warna sedemikian rupa yang edgenya merah sama warna verteksnya dan yang edgenya biru beda warna verteksnya.

Apakah ini selalu dapat dilakukan? TIDAK. Jika kita lihat pada subgraf C-E-F:

• Misalkan E diwarnai oleh warna yang pertama. Maka C dan F pun harus sama, yaitu warna pertama. Namun hubungan C-F menyatakan bahwa warnanya harus beda. Tentu jelas bahwa ini suatu kontradiksi yang terang-terangan. Hubungan C-F selalu false jika kita memaksimalisasikan banyaknya edge yang true.
• Misalkan C diwarnai oleh warna yang pertama. Maka E diwarnai oleh warna pertama dan F diwarnai oleh warna kedua. Namun hubungan E-F selalu false.

Dua poin ini memenuhi pertanyaan yang diminta soal. Kita dapatkan banyaknya konfigurasi adalah 2⁴ dikalikan dengan 2⁵, alias 512.