tuturwidodo..com

tuturwidodo..com

21 June 2013

Solusi Nomor 10 OSN Matematika SMP Tahun 2013

Ditulis Oleh pada 21 June 2013


Soal Nomor 10 OSN Matematika SMP 2013

Sebuah tabel yang berukuran $n$ baris dan $n$ kolom akan diisi dengan bilangan $1$ atau $-1$ sehingga hasil kali semua bilangan yang terletak dalam setiap baris dan hasil kali semua bilangan yang terletak dalam setiap kolom adalah $-1$. Berapa banyak cara berbeda untuk mengisi tabel tersebut?


Penyelesaian :

Misalkan $a_{ij}$ menyatakan bilangan pada baris ke-$i$, kolom ke-$j$. Pertama - tama isi terlebih dahulu tabel $(n-1)\times(n-1)$ yang pertama dengan $1$ atau $-1$. Banyaknya cara pengisian jelas ada $2^{(n-1)^2}$. Selanjutnya untuk bilangan - bilangan yang diisikan pada kolom terakhir yaitu kolom ke-$n$ ada tepat satu pilihan, menyesuaikan agar perkalian setiap baris ke-$i$ sama dengan $-1$. Sebagai contoh untuk $a_{1n}$ nilainya tergantung dari hasil $\prod\limits_{i=1}^{n-1} a_{1i}$. Oleh karena itu pengisian bilangan- bilangan pada kolom ke-$n$ adalah unik untuk setiap cara pengisian pada tabel $(n-1)\times(n-1)$ yang pertama. Demikian pula untuk pengisian bilangan - bilangan pada baris ke-$n$ juga unik.

Dari sini dapat dilihat bahwa banyaknya cara pengisian tabel $n\times n$ sesuai kriteria pada soal ada maksimal $2^{(n-1)^2}$. Mengapa demikian? Sebab untuk setiap cara pengisian yang diperoleh dari tabel $(n-1)\times(n-1)$ yang pertama, bisa jadi kita tidak dapat mengisi kolom ke-$n$ dan baris ke-$n$ sehingga dipenuhi kriteria pada soal. Apa masalahnya? Tentu saja mudah dilihat bahwa untuk mengisi kolom ke-$n$ dari $a_{1n}$ sampai dengan $a_{(n-1)n}$ atau untuk mengisi baris ke-$n$ dari $a_{n1}$ sampai dengan $a_{n(n-1)}$ tidak ada masalah. Masalahnya terletak pada bilangan $a_{nn}$ karena nilainya ditentukan oleh $\prod\limits_{i=1}^{n-1} a_{in}$ dan $\prod\limits_{i=1}^{n-1} a_{ni}$. Dengan kata lain, untuk menjamin bahwa untuk setiap cara pengisian dari tabel $(n-1)\times(n-1)$ yang pertama, kita selalu bisa mengisi bilangan - bilangan pada kolom ke-$n$ dan baris ke-$n$ sehingga kondisi pada soal terpenuhi, harus dibuktikan bahwa $$\begin{equation*} \prod\limits_{i=1}^{n-1} a_{in}=\prod\limits_{i=1}^{n-1} a_{ni} \end{equation*}$$ Untuk itu, misalkan $A$ adalah hasil perkalian semua bilangan yang diisikan pada tabel $(n-1)\times(n-1)$ yang pertama. Diperoleh $$\begin{equation*} A\times \prod\limits_{i=1}^{n-1} a_{in}=(-1)^{n-1} \end{equation*}$$ demikian pula $$\begin{equation*} A\times \prod\limits_{i=1}^{n-1} a_{ni}=(-1)^{n-1} \end{equation*}$$ Dari kedua kesamaan di atas diperoleh $$\begin{equation*} \prod\limits_{i=1}^{n-1} a_{in}=\prod\limits_{i=1}^{n-1} a_{ni} \end{equation*}$$ seperti yang diharapkan.

Jadi, banyaknya cara pengisian tabel $n\times n$ tersebut adalah $2^{(n-1)^2}$.





1 comments :

  1. Anonymous30 June, 2013

    sertakan juga dong file .pdf nya....
    supaya jadi satu dan kadang latexnya error juga...
    terima kasih

    ReplyDelete