المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۵

دنباله‌یی از اعداد ‎۱‎ تا ‎۹‎ داده شده است. روی این دنباله الگوریتم زیر را انجام می‌دهیم. ابتدا ‎۳‎ عنصر اول دنباله را مرتب می‌کنیم. بعد از آن عناصر سوم و چهارم و پنجم را مرتب می‌کنیم. بعد عناصر پنجم و ششم و هفتم و در نهایت عناصر هفتم و هشتم و نهم را مرتب می‌کنیم. برای چه تعداد از جایگشت‌های اعداد یک تا نه دنباله‌ای که با این روش به‌دست می‌آید، مرتب است؟

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

پاسخ

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

معلوم است که باید در مرحله‌ی اول دو خانه از سه خانه‌ی $A$ اعداد ۱ و ۲ باشند که تعداد طرق جا دادن آن دو رقم در سه خانه‌ی مورد اشاره $\binom{3}{2} \times2!$؛ یعنی ۶ می‌باشد. در مرحله‌ی دوم توجه داریم که در خانه‌ی خالی $A$ و دو خانه‌ی سمت راست $B$ باید دو عدد ۳ و ۴ موجود باشند که تعداد طرق جا دادن آ دو رقم در سه خانه‌ی مورد اشاره نیز برابر ۶ می‌باشد. در مرحله‌ی سوم می‌فهمیم که در خانه‌ی خالی باقی‌مانده از مراحل قبلی و دو خانه‌ی سمت راست $C$ باید دو عدد ۵ و ۶ موجود باشند که تعداد طرق جا دادن آن دو رقم در سه خانه‌ی مورد اشاره نیز برابر ۶ می‌باشد. در مرحله‌ی آخر سه خانه‌ی خالی می‌ماند که باید سه عدد ۸٬۷ و ۹ را در آن سه خانه قرار دهیم که این عمل نیز به ۶ طریق ممکن است. بنابراین تعداد کل حالات برابر $6^4$ یعنی ۱۲۹۶ می‌باشد.


ابزار صفحه