Jump to content
Sign in to follow this  
Zekrom

IMO 2012 NO 3

Recommended Posts

$Permainan$ $tebakan$ $pembohong$ adalah permainan yang dimainkan oleh dua pemain $A$ dan $B$. Aturan permainan tergantung pada dua bagian bilangan bulat positif $k$ dan $n$ yang diketahui kedua pemain. Pada awal permainan $A$ memilih bilangan bulat $x$ dan $N$ dengan $1 \leq x \leq N$. Pemain $A$ menjaga kerahasiaan $x$, dan dengan jujur mengatakan $N$ ke pemain $B$. Pemain $B$ sekarang mencoba untuk mendapatkan informasi tentang $x$ dengan menanyakan kepada pemain $A$ pertanyaan-pertanyaan sebagai berikut: masing-masing pertanyaan berisikan $B$ mengspesifikasikan sebarang himounan $S$ dari bilangan bulat positif (dimungkinkan himpunan itu telah dispesifikasikan di beberapa pertanyaan sebelumnya), dan menanyakan kepada $A$ apakah $x$ di dalam $S$. Pemain $B$ boleh bertanya sebanyak mungkin pertanyaan sesuai keinginannya. Setelah masing-masing pertanyaan, pemain $A$ harus segera menjawab pertanyaan itu dengan $ya$ atau $tidak$, tetapi diperbolehkan untuk berbohong sebanyak yang dia inginkan; satu-satunya batasan adalah bahwa, diantara sebarang $k+1$ jawaban berturutan, setidaknya satu jawaban harus benar.

Setelah $B$ mengajukan sebanyak mungkin pertanyaan-pertanyaan yang dia inginkan, dia harus mengspesifikasikan himpunan $X$ beranggotakan paling banyak $n$ bilangan bulat positif. Jika $x$ di dalam $X$ maka $B$ menang; jika tidak, ia kalah. Buktikan bahwa:

1. Jika $n \geq 2^k$, maka $B$ dapat menjamin suatu kemenangan.

2. Untuk semua $k$ cukup besar, terdapat suatu bilangan bulat $n \geq (1,99)^k$ sehingga $B$ tidak dapat menjamin suatu kemenangan.

Edited by Zekrom

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  

×