سؤال ۱۵

همه‌ی رشته‌های تولید شده از حروف $a$ و $b$ را به ترتیبِ طول رشته و در صورت مساوی بودن طول‌ها به ترتیب الفبایی مرتب می‌کنیم. مثلاً هشت رشته‌ی اول عبارت‌اند از: $a,b,aa,ab,ba,bb,aaa,aab$. رشته‌ی ۱۳۸۱ام کدام است؟

  1. $ababbaabba$
  2. $bababbbab$
  3. $ababbaabab$
  4. $babaabbaab$
  5. $ababaaaba$

پاسخ

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

معلوم است که تعداد رشته‌های به طول $i$ برابر$2^i$ می‌باشد. بنابراین آخرین رشته ۹ حرفی که به صورت $bbbbbbbbb$ می‌باشد رشته هزار و بیست و دوم می‌باشد زیرا:

$$2+4+8+16+32+64+128+256+512=1022$$

به تعداد $2^{10}$ رشته ده حرفی می‌توان ساخت که نصف آن‌ها با حرف $a$ و نصف دیگر با حرف $b$ شروع می‌شوند و چون رشته ۱۳۸۱ ام به نصفه اول متعلق است٬ بنابراین آن رشته با حرف $a$ شروع می‌شود. لازم به ذکر است که رشته مورد نظر سیصد و پنجاه و نهمین رشته ده حرف است٬ زیرا $1381-1022=359$ در بین ۵۱۲ رشته‌ای که با $a$ شروع می‌شوند ۲۵۶ تای اول آن‌ها حرف دوم $a$ و ۲۵۶ تای دیگر(که ۳۵۹ نیز به همین دسته متعلق است) حرف دوم $b$ دارند(چون $359-256=103<128$ ، بنابراین رشته مورد نظر به دسته اول تعلق دارد). اگر به همین ترتیب ادامه دهیم خواهیم داشت:

حرف اول=$a$ $1381-1022=359<512 \Rightarrow$

حرف دوم=$b$ $359>256 \Rightarrow$

حرف سوم=$a$ $359-256=103<128 \Rightarrow$

حرف چهارم=$b$ $103>64 \Rightarrow$

حرف پنجم=$b$ $103-64=39>32 \Rightarrow$

حرف ششم=$a$ $39-32=7<16 \Rightarrow$

حرف هفتم=$a$ $7<8 \Rightarrow$

حرف هشتم=$b$ $7>4 \Rightarrow$

حرف نهم=$b$ $7-4=3>2 \Rightarrow$

حرف دهم=$a$ $3-2=1<7 \Rightarrow$