المپدیا

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

ابزار کاربر

ابزار سایت


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

روی یک دایره اعداد ‎۱‎ تا ‎۸‎ را به‌ترتیب ساعت‌گرد چیده‌ایم. از عدد ‎۱‎ شروع می‌کنیم و در هر مرحله یا به‌عدد بعدی (در جهت ساعت‌گرد) می‌رویم و یا از روی عدد بعدی می‌پریم و به‌عدد پس از آن می‌رویم. وقتی که دوباره به ‎۱‎ رسیدیم متوقف می‌شویم. می‌دانیم که ازابتدای کار تا این‌لحظه ‎۱‎ بار از روی ‎۴‎ پریده‌ایم. به‌چند حالت ممکن است این کار را کرده باشیم؟

  1. کم‌تر از ‎۵۰۰‎ طریق
  2. بین ‎۵۰۰‎ و ‎۱۰۰۰‎ طریق
  3. بین ‎۱۰۰۱‎ و ‎۲۰۰۰‎ طریق
  4. بین ‎۲۰۰۱‎ و ‎۴۰۰۰‎‎ طریق
  5. بیش‌تر از ‎۴۰۰۰‎‎ طریق

پاسخ

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

حرکت دو دور کامل انجام یافته است که ‌آن را به صورت ردیفی٬ به شکل زیر نمایش می‌دهیم:

$$(1),\underline{2},\underline{3},\underline{4},\underline{5},\underline{6},\underline{7},(8),1,(2),\underline{3},\underline{4},\underline{5},\underline{6},\underline{7},\underline{8},(1)$$

در نمایش فوق $(x)$ نشانگر آن است که در جایگاه $x$ توقف یقینا انجام شده است و $\underline{y}$ نشانگر آن است که جایگاه $y$ قابل توقف است. اگر تعداد پرش‌های دور اول صفر باشد آن حرکت به $\binom{6}{0}$؛ یعنی ۱ طریق ممکن است. اگر تعداد پرش‌های دور اول یک بار باشد انتخاب آن جایگاه به $\binom{6}{1}$؛ یعنی ۶ طریق ممکن است. اگر تعداد پرش‌های دور اول دو بار باشدانتخاب ان دو جایگاه به $\binom{6}{2}-5$؛ یعنی ۱۰ طریق ممکن است و بالاخره اگر تعداد پرش‌های دور اول سه بار باشد انتخاب آن سه جایگاه به ۴ طریق (۲۴۶ یا ۲۴۷ یا ۲۵۷ یا ۳۵۷) ممکن است که مجموع کل آن طرق برابر ۲۱ می‌شود. معلوم است که تعداد پرش‌های دور اول ۴ یا بیش‌تر نمی‌تواند باشد. تعداد طرق پرش‌ها در دور دوم مستقل از دور اول نیز برابر ۲۱ می‌شود که طبق اصل ضرب تعداد کل طرق برابر $21\times21$؛ یعنی ۴۴۱ خواهد شد.


ابزار صفحه