سوال ۱۴
پیمان یک سکه را در یکی از خانههای یک جدول ۴ × ۴ پنهان کرده است. جبار از محل سکه بیاطلاع است، اما دستگاه فلزیابی دارد که میتواند به کمک آن محل سکه را پیدا کند. در هر مرحله، جبار میتواند دستگاه را روی ۴ خانهی جدول که به صورت یک $L$ قرار گرفتهاند بگذارد. او میتواند دستگاه را بچرخاند یا وارونه کند (برای مثال دو تا از حالتهای قرارگیری دستگاه در شکل نشان داده شده است). اگر سکه در یکی از این ۴ خانه باشد، دستگاه بوق میزند و اگر نباشد، دستگاه هیچ واکنشی نشان نمیدهد. جبار حداقل چند بار باید از دستگاه استفاده کند تا به طور تضمینی بتواند محل سکه را مشخص کند؟
- ۴
- ۸
- ۵
- ۷
- ۶
پاسخ
گزینهی ۳ درست است.
میتوان نشان داد این تعداد لازم است. اگر در اولین مرحله دستگاه بوق نزند، ۴ خانه را میتوان به طور تضمینی حذف کرد. در هر یک از مراحل بعدی، میتوان از حذف حداکثر نصف خانهها اطمینان داشت. پس به حداقل ۴ مرحلهی دیگر نیاز داریم. لذا در مجموع ۵ مرحله لازم است.
برای پیدا کردن سکه با ۵ مرحله، ابتدا جبار ۳ بار دستگاه را به اشکال زیر روی جدول قرار میدهد.
در صورتی که دستگاه در یکی از مراحل بوق بزند، مکان سکه به آن ۴ خانه محدود میشود و اگر در هیچ مرحلهای بوق نزند، سکه در یکی از ۴ خانهی باقیمانده است. کافی است او در مرحلهی بعد دستگاه را به نحوی قرار دهد که با ۲ خانه از خانههای ممکن برای وجود سکه اشتراک داشته باشد. با استدلالی مشابه، محل احتمالی سکه به ۲ خانه از جدول کاهش مییابد. در نهایت، با قرار دادن دستگاه به نحوی که با خانههای احتمالی وجود سکه تنها یک اشتراک داشته باشد، مکان سکه مشخص میشود.
| < سوال قبل | سوال بعد > |