المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۲

جدول رو‌به‌ٰرو به ما داده شده است. در هر مرحله می توانیم تغییری در این جدول بدهیم. تغییرات به این صورت است که جای دوسطر یا جای دو ستون را عوض می کنیم. با استفاده از این تغییرات به چند جدول مختلف می توانیم برسیم؟توجه کنید که تغییرات را به تعداد دلخواه می توانیم انجام دهیم.

  1. ۱۴۴
  2. ۹۶
  3. ۵۷۶
  4. ۲۸۸
  5. ۲۴

پاسخ

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

در ابتدا تعداد یک‌های سطرها و همچنین ستون‌ها برابر مجموعه‌ی ${1,2,3,4}$ است. در هر مرحله اگر جای دو سطر (ستون) را عوض کنیم این مجموعه نه برای ستون‌ها و نه برای سطرها تغییری نمی‌کند.

از طرفی با حرکات ذکرشده هر جایگشتی از این مجموعه را می‌توان تولید کرد (چرا؟).

اگر جایگشت سطر و ستون‌ها را بدانیم، جدول به صورت یکتا مشخص می‌شود. چرا که اعداد سطر و ستون با شماره‌ی ۴ همه یک هستند و در نتیجه اعداد سطر و ستون با شماره‌ی ۱ نیز بدست می‌آید. پس از آن اعداد سطر و ستون با شماره‌ی ۳ و در نهایت بقیه اعداد بدست می‌آیند.

پس با توجه به نکات بالا تعداد جداول مختلف برابر است با:

$$(4!)^2=576$$


ابزار صفحه