Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۸

یک جایگشت مرتبه‌ی n دنباله‌ای (ترتیبی) از اعداد ۱ تا n است. برای مثال ۳,۱,۴,۲ یک جایگشت مرتبه‌ی ۴ است. جدول ضرب یک جایگشت P=p1,p2,...,pn یک جدول n×n است که مقدار خانه‌ی سطر iاُم و ستون jاُم آن برابر pi×pj می‌باشد. برای مثال٬‌ جدول ضرب جایگشت ۳,۱,۲ به صورت شکل مقابل است.

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

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

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

پاسخ

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

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

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

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

P=p12×p22×p3××p8

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

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


ابزار صفحه