المپدیا

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

ابزار کاربر

ابزار سایت


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

دنباله‌های زیر را که از راست به چپ نوشته شده‌اند در نظر بگیرید:

این دنباله‌ها به این صورت ساخته شده‌اند: دنباله‌ی اول ‎۱‎ است. چون دنباله‌ی اول شامل یک ‎«یک»‎ است، دنباله‌ی دوم ‎۱‎، ‎۱‎ است. چون دنباله‌ی دوم شامل دو ‎«یک»‎ است، دنباله‌ی سوم ۱٬۲ است. چون دنباله‌ی سوم شامل یک ‎«دو»‎ و یک ‎«یک»‎ است، دنباله‌ی چهارم ۱٬۱٬۲٬۱ است. چون دنباله‌ی چهارم شامل یک ‎«یک»، یک ‎«دو»‎ و دو ‎«یک»‎ متوالی است، دنباله‌ی پنجم ۱٬۲٬۲٬۱٬۱٬۱ است. و به همین صورت بقیه‌ی دنباله‌ها نیز ساخته می‌شوند‎. \[ \begin{array}{ l l l l l l }‎ ‎1 \\‎ ‎1‎, 1 \\‎ ‎1‎, 2 \\‎ ‎1‎, 1‎, 2‎, 1 \\‎ ‎1‎, ‎ 2, ‎ 2‎, ‎ 1‎, ‎ 1‎, 1 \\‎ ‎1‎, 1‎, ‎ 2‎, 2‎, 1‎, 3‎ \end{array}‎ \]

اولین دنباله‌ای که در آن عدد ‎۴‎ ظاهر می‌شود، دنباله‌ی شماره‌ی چند است؟

  1. ۱۰
  2. ۱۲
  3. ۸
  4. ۱۶
  5. هیچ‌کدام

پاسخ

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

عادد ۴ هرگز ظاهر نخواهد شد. زیرا اولین ۴ وقتی ظاهر خواهد شد که در سطر قبلی ۴ عدد ۱ یا ۲ و یا ۳ به صورت متوالی ظاهر شده باشد. به عنوان مثال اگر ۴ عدد ۲ ظاهر شده باشد و عدد بعد از این ۲ها $a$ و عدد قبل از ۲ها $b$ باشد٬ آن‌گاه این دنباله دو حالت خواهد داشت:

  1. سطر قبل از این دنباله شامل $a...$«۲» و دو «۲» و دو «$b$» و … می‌باشد که طریقه‌ی شمارش درست نیست چون ۲ها را باهم نشمرده‌ایم یعنی یکبار گفته‌ایم $a$ تا «۲» و بلافاصله گفته‌ایم دو تا «۲» که صحیح نمی‌باشد.
  2. سطر قبل از این دنباله شامل …$a$«۲» و دو «۲» و $b$… می‌باشد که باز طریقه‌ی شمارش درست نیست چون در شمارش دو تا «۲» و دو تا «۲» بلافاصله پشت سر هم آمده‌اند.

ابزار صفحه