-_-

OSN SMA 2017 No 8

4 posts in this topic

Lantai dari sebuah aula ditutupi dengan $2017\times2017$ ubin satuan. Luffy mempunyai sejumlah detektor. Setiap detektor yang diletakkan di atas ubin akan menyala jika tepat dibawahnya terdapat emas, dan tidak bereaksi apapun jika tidak ada emas di bawahnya. Luffy meletakkan $k$ buah detektor tepat di atas $k$ buah ubin kemudian dia keluar ruangan. Kemudian Sanji memilih suatu daerah persegi yang ditutupi oleh $1500 \times 1500$ ubin satuan dan menyembunyikan tepat satu koin emas di bawah setiap ubin.  Ketika Luffy kembali dan melihat detektor yang tadi dia pasang, dia dapat menentukan letak semua koin yang tadi di tanam Sanji.


 Tentukan nilai $k$ terkecil agar Luffy selalu dapat menentukan letak semua koin tak peduli daerah manapun yang dipilih Sanji.

0

Share this post


Link to post
Share on other sites

Intuisi saya, bikin "salib" di tengah2 persis, jadi dari situ daerah yang dipilih Sanji (posisi horizontal dan vertical nya) bisa ketahuan persis.

Nah sekarang, karena 1500x1500 itu mayan gede, benernya salib yang di tengah2 aula nggak perlu kan, jadi bisa bolong gede gitu. Terus sekarang, sisanya juga tidak harus berturut2... tapi bisa selang satu ubin (every other tile), jadi tetap ketahuan daerah yang dipilih Sanji di mana.

 

Saya belum kepikir membuktikan ini minimalnya bagaimana.... mungkin pakai pendekatan, bahwa ada sekian cara memilih region yang bisa dipilih oleh Sanji, sedangkan setiap detektor hanya bisa memberi 2 kemungkinan: nyala atau tidak, jadi k detektor akan memberi 2^k jawaban yang mungkin.

0

Share this post


Link to post
Share on other sites
On 7/5/2017 at 9:28 PM, hendrata said:

Intuisi saya, bikin "salib" di tengah2 persis, jadi dari situ daerah yang dipilih Sanji (posisi horizontal dan vertical nya) bisa ketahuan persis.

Nah sekarang, karena 1500x1500 itu mayan gede, benernya salib yang di tengah2 aula nggak perlu kan, jadi bisa bolong gede gitu. Terus sekarang, sisanya juga tidak harus berturut2... tapi bisa selang satu ubin (every other tile), jadi tetap ketahuan daerah yang dipilih Sanji di mana.

 

Saya belum kepikir membuktikan ini minimalnya bagaimana.... mungkin pakai pendekatan, bahwa ada sekian cara memilih region yang bisa dipilih oleh Sanji, sedangkan setiap detektor hanya bisa memberi 2 kemungkinan: nyala atau tidak, jadi k detektor akan memberi 2^k jawaban yang mungkin.

Menurut saya jika memakai salib, tidak mungkin salib itu kecil, pasti akan besar. Menurut saya jawabannya adalah 2017. Luffy bisa meletakkan detektor di sepanjang diagonal ubin aula $2017 \times 2017$. Jika luffy ingin tahu dimana semua koin emasnya, dia hanya tinggal melacak dengan mencari diagonal yang menyala. Ubin dengan detektor menyala yang paling ujung harusnya sudut atau ubin atasnya sudut ubin $1500 \times 1500$. Sehingga sisa sisi lain dengan mudah dicari. Jika masih bingung maksud saya, coba digambar aja diagonalnya terus misalnya ubin dalam diagonal yang menyala hanya ubin A, B, sekian yg anda mau. Coba Anda cari persegi $1500 \times 1500$ setelah menentukan diagonal yang menyala.

0

Share this post


Link to post
Share on other sites

Jawabannya 1034; letakkan detektor di $(1000, n)$ dan $(n, 1000)$ untuk $1 \le n \le 517$. Buktinya gunakan fakta bahwa dalam sebuah persegi panjang $1500 \times 2017$, harus ada minimal 517 detektor yang tidak di dalam persegi panjang $1500 \times 983$ di tengah.

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