سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۹
سوال ۹
مسئله‌ی قبل را در نظر بگیرید (سوال۸)٬ با این تفاوت که اولاً٬ مرتبه‌ی کار به جای ٬۸ برابر ۳ است. ثانیاً٬ آیدا به جای یک جایگشت٬ دو جایگشت مانند $P = \langle p_1, p_2, p_3 \rangle$ و $Q = \langle q_1, q_2, q_3 \rangle$ را انتخاب می‌کند و عدد سطر $i$اُم و ستون $j$اُم جدول برابر $p_i \times q_j$ است. برای مثال٬ جدول ضرب دو جایگشت $P = \langle ۱, ۳, ۲ \rangle$ و $Q = \langle ۲, ۱, ۳ \rangle$ مطابق شکل مقابل است.
آیدین در صورتی در این مسئله برنده می‌شود که بتواند هر دو جایگشت $P$ و $Q$ را حدس بزند. کم‌ترین مقدار $k$ که آیدین بتواند همواره برنده بشود چند است؟
- ۲
- ۳
- ۴
- ۵
- ۶
پاسخ
گزینه‌ی (۲) درست است.
۳ پرسش لازم و کافی است.
- اثبات لزوم شرط: فرض کنید بتوان با دو پرسش بتوان این‌کار را انجام داد. در صورتی که هر دو در یک سطر یا ستون باشند، حداقل دو عنصر از یک جایگشت سوال نشده‌اند و در نتیجه مسئله کامل حل نشده است. اگر این دو اشتراکی نداشته باشند، فرض کنید عدد آن‌ها ۲ و ۶ باشند. در این حالت نمی‌توان بقیه‌ی جدول را به‌صورت یکتا به‌دست آورد. پس حداقل سه پرسش لازم است.
- اثبات کافی بودن شرط: ابتدا دو خانه از سطر اول را بپرسید. باتوجه به این دو، عدد سوم سطر به‌صورت یکتا مشخص می‌شود (مجموعه‌ی حالات سطرها با یک‌دیگر در دو عضو اشتراک ندارند). در نتیجه یک جایگشت و یکی از اعداد یکی از جایگشت‌ها مشخص می‌شود. سپس با پرسیدن یک خانه‌ی دیگر می‌توان عدد دیگر جایگشت را فهمید و در نتیجه تنها عدد باقی‌مانده نیز به‌دست می‌آید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
