المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۸

سوال ۸

یک جایگشت مرتبه‌ی $n$ دنباله‌ای (ترتیبی) از اعداد ۱ تا $n$ است. برای مثال $\langle ۳, ۱, ۴, ۲ \rangle$ یک جایگشت مرتبه‌ی ۴ است. جدول ضرب یک جایگشت $P = \langle p_1, p_2, ..., p_n \rangle$ یک جدول $n\times n$ است که مقدار خانه‌ی سطر $i$اُم و ستون $j$اُم آن برابر $p_i \times p_j$ می‌باشد. برای مثال٬‌ جدول ضرب جایگشت $\langle ۳, ۱, ۲ \rangle$ به صورت شکل مقابل است.

آیدا و آیدین بازی زیر را انجام می‌دهند. ابتدا آیدین از اتاق بیرون می‌رود و آیدا یک جایگشت مرتبه‌ی ۸ انتخاب می‌کند و جدول ضرب آن را می‌نویسد و بر روی هر کدام از ۶۴ خانه‌ی جدول یک سکه می‌گذارد.

آیدین به اتاق برمی‌گردد و $k$ تا از خانه‌های جدول را انتخاب می‌کند و از آیدا می‌خواهد تا سکه‌های آن $k$ خانه را هم‌زمان از روی صفحه بردارد. بعد از انجام این کار٬ اگر آیدین بتواند جایگشت آیدا را دقیقا تعیین کند٬‌ برنده می‌شود. کم‌ترین مقدار $k$ که آیدین بتواند همواره برنده بشود چند است؟

  1. ۴
  2. ۵
  3. ۶
  4. ۷
  5. ۸

پاسخ

گزینه (۳) درست است.

۶ سوال لازم و کافی است.

مثال: فرض کنید ضرب عدد اول با اعداد سوم و چهارم را بپرسیم. همچنین ضرب عدد دوم با اعداد پنجم تا هفتم را بپرسیم و در نهایت ضرب اعداد هفتم و هشتم را نیز بپرسیم (در مجموع شش پرسش انجام داده‌ایم).

اگر چهار پرسش اول را در پرسش ششم ضرب کنیم و حاصل را $P$ بنامیم، داریم:

$$P={p_1}^2×{p_2}^2×p_3×…×p_8$$

در نتیجه اگر عدد حاصل را بر $8!$ تقسیم کنیم حاصل برابر $p_1×p_2$ می‌شود. حال اگر هر سه پرسش با جایگشت متفاوت را در هم ضرب کنیم ضرب دو عنصر دیگر (همانند قبلی) بدست می‌آید. بدین ترتیب می‌توان ضرب اعداد سوم و چهارم با اعداد پنجم و ششم را متوجه شد.

به همین روند می‌توان ضرب عدد اول و هفتم را فهمید. در نتیجه چون ضرب هر دوتایی از اعداد اول و ششم و هفتم را داریم می‌توان هرکدام از آن‌ها را به‌دست آورد. پس چون ضرب دوتایی این اعداد را داریم هر عدد نیز به صورت مستقل به‌دست خواهد آمد.


ابزار صفحه