Jump to content
Sign in to follow this  
Adri

Soal KSM no 4 Extended

Recommended Posts


Diberikan $n$ adalah bilangan asli. Terdapat $n$ buah bilangan bulat di papan tulis yang semuanya ditulis dalam satu baris. Kemudian, untuk setiap bilangan di papan tulis, katakanlah bilangan tersebut $x$, Ali menghitung berapa banyak bilangan yang lebih kecil dari $x$ yang pada papan tulis tersebut letaknya berada disebelah kanan $x$. Kemudian dia menulis angka hasil perhitungannya tersebut tepat dibawah $x$. Sehingga diperoleh baris baru yang memuat $n$ buah bilangan bulat. Kemudian prosedur serupa dilakukan kepada $n$ buah bilangan pada baris yang baru ini. 

Buktikan bahwa berapapun $n$ buah bilangan yang ditulis diawal, maka dengan menggunakan prosedur diatas berkali-kali, pada suatu saat $n$ bilangan baru yang dihasilkan akan tepat sama dengan $n$ bilangan yang berada di baris sebelumnya.

 

 

Extended question : Buktikan bahwa semua baris yang selalu sama dengen sebelum nya dapat diperoleh  cukup dengan menggunakan maksimal $n-1$ langkah.

Share this post


Link to post
Share on other sites
Spoiler

Akan dibuktikan dengan metode induksi. 

Kasus dasar nya jelas

Misalkan untuk $n$ pernyataan benar, akan dibuktikan untuk $n+1$ pernyataan tetap benar.

Lihat suku paling kiri dan kedua paling kiri, misalkan $a$ dan $b$ secara berturut-turut.

Jika $a=b$, maka setelah berapapun operasi jelas nilai bilangan di kedua tempat tersebut tetap sama.

jika $a<b$, maka jelas bilangan paling kiri akan selalu lebih kecil sama dengan bilangan kedua paling kiri. Jadi yang paling kiri gaakan mandang kedua dari kiri dibawahnya. Jadi bisa dipisah $a(sama n-1 sisanya)$ dan $b(sama n-1 sisanya)$. Jelas proses ini harus udah terminated di step $n-1<n$ maka induksi berhasil

jika $a>b$, perhatikan kalau setelah satu step bilangan di paling kiri lebih besar sama dengan $1$, setelah $2$ step lebih besar sama dengan $2$, dst setelah step ke $n$ nilainya lebih besar sama dengan $n$, maka udah maks, berarti karena $n$ yang di kanan pasti udah terminate (dari induksi) dan nilai yang dikiri udah max, maka di step ke $n$ pasti terminate. 

 

Induksi selesai.

 

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  

×