دست‌کش‌های مشکوک
حسام یک دست‌کش آبی در دست راست و یک دست‌کش قرمز در دست چپ خود دارد. پیام و حسام یک عدد طبیعی $n$ انتخاب می‌کنند ($n \ge 2$)؛ سپس حسام یک عدد طبیعی $k$ برمی‌گزیند که $1 \le k \le n$ باشد و پیام باید $k$ را بفهمد. در هر مرحله پیام می‌تواند یکی از دو پرسش زیر را از حسام بپرسد:
- دست‌کش دست راست تو چه رنگی است؟
- دست‌کش دست چپ تو چه رنگی است؟
حسام در هر پرسش، یکی از دو پاسخ «قرمز» یا «آبی» را می‌گوید. پرسش‌های پیام را به ترتیب با شماره‌های $1, 2, \ldots, q$ شماره‌گذاری کنید. روش پاسخ‌گویی حسام به این صورت است که او پاسخ $k$ پرسش نخست پیام را به طور دل‌خواه می‌دهد (دروغ یا راست)؛ سپس به ازای هر $i > k$، در پاسخ پرسش شماره‌ی $i$، پاسخ درست پرسش شماره‌ی $i-k$ را می‌دهد. توجه کنید پاسخ $k$ پرسش نخست به صورت دل‌خواه داده می‌شود و حسام هیچ روش از پیش تعیین شده‌ای برای پاسخ‌گویی به آن ندارد.
توجه کنید پیام دست‌کش‌های حسام را می‌بیند و هم‌چنین از روش پاسخ‌گویی حسام آگاه است؛ امّا $k$ را نمی‌داند و با توجه به پاسخ‌های حسام باید آن را بفهمد. کمینه‌ی تعداد پرسش‌هایی که پیام باید بپرسد تا به طور تضمینی $k$ را بفهمد، چیست؟ پاسخ را بر حسب $n$ بیابید.
پاسخ
ثابت می‌کنیم پاسخ برابر $n+1$ است.
ابتدا ثابت می‌کنیم پیام روشی تضمینی با کم‌تر از $n+1$ پرسش ندارد. از برهان خلف استفاده می‌کنیم. فرض کنید پیام با $m\le n$ پرسش به هدف خود رسیده است. اگر پاسخ حسام برای پرسش آخر برابر با پاسخ درست پرسش نخست شده باشد، در این صورت اگر $m=1$ باشد، مقدار $k$ می‌تواند هر یک از اعداد $1, 2$ و اگر $m\neq1$ باشد، مقدار $k$ می‌تواند هر یک از اعداد $m$ یا $m-1$ (و حتّی اعدادی دیگر) باشد. پس پیام نمی‌تواند به طور یکتا $k$ را تشخیص دهد که تناقض است و حکم اثبات می‌شود. $\blacksquare$
حال ثابت می‌کنیم پیام می‌تواند با حداکثر $n+1$ پرسش به هدف خود برسد. پیام در پرسش نخست خود رنگ دست‌کش دست راست حمید و در بقیه‌ی پرسش‌ها رنگ دست‌کش دست چپ او را می‌پرسد. ادّعا می‌کنیم پس از این $n+1$ پرسش $k$ به طور یکتا تعیین می‌شود. از برهان خلف استفاده می‌کنیم. فرض کنید این طور نباشد؛ یعنی دست کم دو عدد مثل $p, q$ وجود دارند که مقدار $k$ می‌تواند برابر با آن‌ها باشد. بدون از دست دادن کلیت مسئله فرض کنید $p > q$ باشد. از آن‌جایی که $q$ نامزدی برای $k$ است، پس پاسخ پرسش $q+1$ باید آبی و پاسخ پرسش‌های $q+2, q+3, \ldots, n+1$ باید قرمز باشد؛ بنابراین پاسخ پرسش $p+1$ نیز قرمز است؛ زیرا $p+1 \ge q+2$. از طرفی $p$ نیز نامزدی برای $k$ است؛ پس پاسخ پرسش $p+1$ باید آبی باشد. این یک تناقض است و حکم ثابت می‌شود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
