Jump to content
Sign in to follow this  
hendrata

Tebak-tebakan lagi: Nol di papan catur

Recommended Posts

Sekarang Wati memiliki papan catur $n \times n$ yang diisi dengan bilangan real sedemikian sehingga:


1. Ada tepat satu bilangan nol di papan itu


2. Bilangan2 pada setiap kolom berurutan (monoton tidak turun) dari atas ke bawah


3. Bilangan2 pada setiap baris berurutan (monoton tidak turun) dari kiri ke kanan


 


Tugas Jono adalah mencari tahu di mana lokasi bilangan nol. Ia boleh menebak lokasi bilangan nol tersebut, dan sesudah setiap tebakan, Wati akan memberi tahu bilangan yang terletak di lokasi yang ditebak Jono. Permainan berakhir ketika Jono berhasil menebak lokasi bilangan nol.


 


A. Buktikan bahwa Jono memiliki strategi yang menjamin penemuan bilangan nol sesudah paling banyak $2n-1$ tebakan.


 


B. Buktikan bahwa tidak ada strategi yang menjamin penemuan bilangan nol sesudah $2n-2$ tebakan.


  • Upvote 1

Share this post


Link to post
Share on other sites

coba yang A ya, 



Jelas kalau untuk grid berukuran $1\times K$, $K$ buah langkah cukup untuk menjamin penemuan bilangan nol.


kita akan gunakan sedikit induksi.


perhatikan kalau pada grid $2\times 1$, $2$ langkah cukup untuk menjamin penemuan bilangan nol, dan pada grid $2\times 2$, $3$ langkah cukup untuk menjamin penemuan bilangan nol.


Akan dibuktikan kalau pada grid berukuran $2\times K$, $K+1$ langkah cukup untuk menjamin penemuan bilangan nol untuk setiap $K>2$.


misalkan pada grid $2\times M$, $M+1$ langkah cukup untuk menjamin penemuan bilangan nol untuk setiap $K>M \ge 1$


observasi grid $2\times K$.


kita pilih kotak yang berada pada ujung kanan atas dan ujung kiri bawah.


jika bilangan pada ujung kanan atas positif, maka kolom paling kanan berisi bilangan positif, berarti tidak ada angka 0, kita sebut ini kondisi $a$.


jika bilangan pada ujung kanan atas negatif, maka baris paling atas berisi bilangan negatif, berarti tidak ada angka 0, kita sebut ini kondisi $b$.



jika bilangan pada ujung kiri bawah positif, maka baris paling bawah berisi bilangan positif, berarti tidak ada angka 0, kita sebut ini kondisi $c$.


jika bilangan pada ujung kiri bawah negatif, maka kolom paling kiri berisi bilangan negatif, berarti tidak ada angka 0, kita sebut ini kondisi $d$.


(note: kondisi $a,b,c,d$ ini akan dipakai berkali-kali pada solusi ini) (note: jika saat memilih dua bilangan ini kita menemukan angka 0, kita langsung selesai)


jika yang terjadi adalah kondisi $a$ dan $c$, maka kita tersisa dengan grid $1\times (K-1)$, yang berarti $K-1$ langkah extra cukup untuk menjamin penemuan bilangan nol, berarti $K+1$ langkah cukup untuk menjamin penemuan bilangan nol.


jika yang terjadi adalah kondisi $a$ dan $d$, maka kita tersisa dengan grid $2\times (K-2)$, yang berarti $K-1$ langkah extra cukup untuk menjamin penemuan bilangan nol, berarti $K+1$ langkah cukup untuk menjamin penemuan bilangan nol.


jika yang terjadi adalah kondisi $b$ dan $d$, maka kita tersisa dengan grid $1\times (K-1)$, yang berarti $K-1$ langkah extra cukup untuk menjamin penemuan bilangan nol, berarti $K+1$ langkah cukup untuk menjamin penemuan bilangan nol.

jika yang terjadi adalah kondisi $b$ dan $c$, maka tidak ada angka 0, berarti kasus ini tidak perlu di konsiderasi.

terbukti kalau pada grid berukuran $2\times K$, $K+1$ langkah cukup untuk menjamin penemuan bilangan nol untuk setiap $K>2$.

 

sekarang akan dibuktikan kalau pada pada grid $H\times T$, maka $H+T-1$ langkah cukup untuk menjamin penemuan bilangan 0.

jelas ini benar untuk $H \le 2$.

misalkan ini benar untuk $H \le K$, akan dibuktikan kalau pada pada grid $(K+1)\times T$, maka $K+T$ langkah cukup untuk menjamin penemuan bilangan 0.

perhatikan kalau ini benar untuk $(K+1)\times 1$ dan $(K+1)\times 2$ memenuhi sifat tersebut. 

misalkan ini benar untuk $T \le R$, akan dibuktikan ini tetap benar untuk $T=R+1$.

observasi grid $(K+1)\times (R+1)$,

kita pilih kotak ujung kanan atas dan ujung kiri bawah.

(kita akan gunakan term kondisi $a,b,c,d$)


jika yang terjadi adalah kondisi $a$ dan $c$, maka kita tersisa dengan grid $K\times R$, yang berarti $K+R-1$ langkah extra cukup untuk menjamin penemuan bilangan nol, berarti $K+R+1$ langkah cukup untuk menjamin penemuan bilangan nol.


jika yang terjadi adalah kondisi $a$ dan $d$, maka kita tersisa dengan grid $(K-1)\times (R+1)$, yang berarti $K+R-1$ langkah extra cukup untuk menjamin penemuan bilangan nol, berarti $K+R+1$ langkah cukup untuk menjamin penemuan bilangan nol.


jika yang terjadi adalah kondisi $b$ dan $d$, maka kita tersisa dengan grid $K\times R$, yang berarti $K+R-1$ langkah extra cukup untuk menjamin penemuan bilangan nol, berarti $K+R+1$ langkah cukup untuk menjamin penemuan bilangan nol.

jika yang terjadi adalah kondisi $a$ dan $c$, maka kita tersisa dengan grid $(K+1)\times (R-1)$, yang berarti $K+R-1$ langkah extra cukup untuk menjamin penemuan bilangan nol, berarti $K+R+1$ langkah cukup untuk menjamin penemuan bilangan nol.


Terbukti kalau pada grid $(K+1)\times (R+1)$, cukup $K+R+1$ langkah untuk menjamin penemuan bilangan nol.

Set $K=R=(N-1)$ maka pada grid $N\times N$ cukup $2N-1$ langkah unutk menjamin penumuan bilangan nol.

 



 



Edited by sayakalah

Share this post


Link to post
Share on other sites

Sepintas bukti anda idenya udah benar. Saya nggak neliti setiap baris ya. Kalo solusi saya, kayak gini:



Misalnya petak $(i,j)$ merujuk petak di baris ke-$i$ dan kolom ke-$j$ (notasi matriks seperti biasa). Algoritmanya seperti ini:


Pertama tebak di $(n,1)$. Jika angka ini positif, naik satu petak ke atas, jika negatif, ke kanan satu petak. Begitu seterusnya sampai ketemu angka nol.


 


Bukti bahwa algoritma ini pasti berakhir: Jika $(i,j)$ melambangkan lokasi dari tebakan terakhir, misalkan $S = i-j$. Perhatikan bahwa mula-mula, $S = n-1$ dan pada setiap langkah, $S$ pasti berkurang sebayak 1. Nilai terkecil $S$ yang mungkin adalah di sel $(1,n)$, yakni ketika $S = 1-n$. Jadi setelah $(n-1)-(1-n)+1 = 2n-1$ langkah, algoritma ini pasti berakhir.


 


Bukti bahwa algoritma ini pasti menemukan angka nol:


Misalkan $A$ melambangkan kejadian bahwa kita menebak kolom angka nol dengan benar (belum tentu barisnya benar), dan $B$ melambangkan kejadian bahwa kita menebak baris dengan benar. Dapat mudah dilihat bahwa jika $A$ atau $B$ terjadi, maka kita pasti menemukan angka nol sesudahnya. Misalnya, begitu $A$ terjadi, maka tebakan kita akan ke atas terus menerus sampai mencapai angka nol, dan sebaliknya begitu $B$ terjadi, kita akan ke kanan terus menerus.


 


Sekarang, misalnya angka nol terletak pada lokasi $(x,y)$, maka $A$ akan terjadi sesudah $(x-1)$ gerakan ke kanan, dan $B$ akan terjadi sesudah $(n-y)$ gerakan ke atas. Setiap gerakan adalah antara ke kanan atau ke atas, maka setelah cukup banyak gerakan, salah satu dari $A$ atau $B$ akan terjadi.


 


 



Share this post


Link to post
Share on other sites

Bukti soal kedua:



Misalkan diagonal sel $(i,j)$ sehingga $i+j = n+1$ kita sebut diagonal mayor (yakni diagonal terpanjang dari kanan atas ke kiri bawah).


Dan diagonal minor adalah $(i,j)$ sehingga $i+j = n$.


 


Sekarang misalnya Wati mengisi semua petak di atas diagonal minor dengan bilangan lebih kecil dari -1, dan semua petak di bawah diagonal mayor dengan bilangan lebih besar dari +1, dan bilangan-bilangan tersebut masih memenuhi kondisi pengurutan.


 


Nah untuk diagonal nya sendiri, perhatikan bahwa jika seluruh diagonal mayor diisi dengan bilangan antara 0 dan 1, dan jika seluruh diagonal minor diisi dengan bilangan antara -1 dan 0, dan nol nya ada di salah satu diagonal (mayor atau minor), maka kondisi pengurutan juga masih terpenuhi. Antara sel di diagonal mayor sendiri (misalnya $(n,1)$ dan $(n-1,2)$) tidak ada relasi yang perlu dipenuhi, demikian antara sel di diagonal minor juga tidak ada relasi yang perlu dipenuhi.


 


Sekarang misalkan Wati tidak pernah menentukan bilangan apa yang terdapat di setiap sel diagonal mayor dan minor SAMPAI JONO MENEBAKNYA. Dengan kata lain, Wati pun tidak tahu di mana nolnya akan terjadi. Saat Jono melaksanakan strateginya, jika ia meminta petak yang bukan di diagonal, Wati memberi nilai petak tersebut. Jika ia meminta sel yang di diagonal mayor, Wati memberi suatu bilangan acak di antara 0 dan 1. Jika ia meminta sel di diagonal minor, Wati memberi bilangan acak di antara -1 dan 0. Perhatikan bahwa dari sudut pandang Jono, semua isi sel yang diberikan Wati masih konsisten dengan kondisi pengurutan.


 


Wati akhirnya hanya "menyerah" dan mengatakan isi petak nol jika tebakan itu adalah tebakan diagonal terakhir. Artinya, jika semua petak diagonal mayor dan minor lainnya sudah ditebak, dan petak ini adalah petak diagonal yang terakhir (yang mana mau tidak mau nol nya harus ada di petak tersebut). Karena ada $2n-1$ petak diagonal mayor dan minor, apapun strategi Jono, Wati selalu bisa "menunda" penemuan angka nol sampai tebakan paling sedikit ke-$2n-1$.


 



Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×