====== سؤال ۱۵======

همه‌ی رشته‌های تولید شده از حروف $a$ و $b$ را به ترتیبِ طول رشته و در صورت مساوی بودن طول‌ها به ترتیب الفبایی مرتب می‌کنیم. مثلاً هشت رشته‌ی اول عبارت‌اند از: $a,b,aa,ab,ba,bb,aaa,aab$. رشته‌ی ۱۳۸۱ام کدام است؟
  - $ababbaabba$
  - $bababbbab$
  - $ababbaabab$
  - $babaabbaab$
  - $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$

</پاسخ>
  * [[سوال ۱۶|سوال بعد]]
  * [[سوال ۱۴|سوال قبل]]