Titik Latis


[OSP 2010] Diberikan n titik pada koordinat dengan nilai x dan y merupakan bilangan bulat (titik latis). Tentukan nilai terkecil dari n sehingga setidaknya terdapat dua titik yang jika dihubungkan maka titik tengahnya merupakan titik latis.

Solusi:

Misalkan 2 titik yang merupakan bagian dari n titik tersebut adalah (x_1,y_1) dan (x_2,y_2), maka koordiant titik tengahnya adalah (\frac{1}{2}(x_1+x_2),\frac{1}{2}(y_1+y_2)

Dikarenakan koordinat titik tengah tersebut merupakan bilangan bulat maka x_1+x_2 dan y_1+y_2 genap, yang hanya bisa terjadi jika paritas x_1 dan paritas x_2 sama, serta paritas y_1 dan paritas y_2 sama.

Balik ke belakang, diketahui bahwa dalam suatu koordinat cartecius, paritas titik yang mungkin adalah (ganjil, ganjil),(ganjil, genap),(genap, ganjil),(genap, genap).  Agar dapat dipastikan bahwa ada 2 titik yang titik tengahnya merupakan titik latis, maka menurut Pigeon Hole Principle nilai n yang mungkin adalah banyaknya paritas titik di atas ditambah 1 atau dengan kata lai 4+1=5. Jadi, n_{(min)}=5

Jawab: 5

About ardiantoarsadi

don't look for miracles it will come

Posted on Juni 7, 2010, in SOAL DAN SOLUSI and tagged , , , . Bookmark the permalink. Tinggalkan komentar.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: