Sign in to follow this  
Followers 0
Tetsu

OSN 2007 No 5 - Meletakkan benteng pada papan catur

2 posts in this topic

Misalkan $r,s$ dua bilangan asli dan $P$ sebuah 'papan catur' dengan $r$ baris dan $s$ lajur. MIsalkan $M$ menyatakan banyak maksimal benteng yang dapat diletakkan pada $P$ sehingga tidak ada dua benteng yang saling menyerang.

  • Tentukan $M$.
  • Ada berapa cara meletakkan $M$ buah benteng pada $P$ sehingga tidak ada dua benteng yang saling menyerang?
0

Share this post


Link to post
Share on other sites

Posted (edited)

Misalkan $p=\min \left( {r,s} \right)$ dan $q=\max \left( {r,s} \right)$. 

Perhatikan bahwa agar tidak ada dua benteng yang saling menyerang maka tidak boleh ada sedikitnya dua benteng yang terletak pada baris atau lajur yang sama. Kita klaim bahwa $M\le p$,  karena jika $M>p$ menurut pigeon hole principle akan ada sedikitnya dua buah benteng yang terletak pada baris atau lajur yang sama.

Misalkan ${{x}_{{ij}}}$ menyatakan petak catur pada baris ke-$i$ lajur ke-$j$ . jika $p$ buah benteng diletakkan pada petak ${{x}_{{kk}}}$  dengan $k=1,2,...,p$ , maka $p$ buah benteng tidak akan saling menyerang.  Jadi kita peroleh $M=p=\min \left( {r,s} \right)$

 

Selanjutnya akan kita hitung banyaknya cara menempatkan $M$ buah benteng tersebut.

-          Jika $p=r$

Cara meletakkan benteng pertama pada baris ke-$1$ ada sebanyak $s$ cara.

Karena benteng pada baris kedua tidak boleh satu lajur dengan benteng pertama, maka Cara meletakkan benteng kedua pada baris ke-$2$ ada sebanyak $s-1$ cara

Cara meletakkan benteng ketiga pada baris ke-$3$ ada sebanyak $s-2$ cara, dst.

Cara meletakkan benteng ke-$r$ pada baris ke-$r$ ada sebanyak $s-r+1$.

Jadi banyaknya cara meletakkan $M$ benteng tersebut adalah

$s\left( {s-1} \right)\left( {s-2} \right)...\left( {s-r+1} \right)=\frac{{s!}}{{\left( {s-r} \right)!}}=\frac{{q!}}{{\left( {q-p} \right)!}}$

-          Jika $p=s$,

Dengan analogi yang sama (pertimbangankan penempatan benteng pada lajur ke-$i$) akan diperoleh banyaknya cara meletakkan $M$ benteng tersebut sebanyak

$r\left( {r-1} \right)\left( {r-2} \right)...\left( {r-s+1} \right)=\frac{{r!}}{{\left( {r-s} \right)!}}=\frac{{q!}}{{\left( {q-p} \right)!}}$

Kesimpulannya cara menempatkan $M$ buah benteng pada papan $P$ sehingga tidak ada dua benteng saling menyerang adalah

$\frac{{q!}}{{\left( {q-p} \right)!}}=\frac{{\max \left( {r,s} \right)!}}{{\left( {\max \left( {r,s} \right)-\min \left( {r,s} \right)} \right)!}}$

Edited by Paryadi
0

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  
Followers 0