همهی رشتههای تولید شده از حروف a و b را به ترتیبِ طول رشته و در صورت مساوی بودن طولها به ترتیب الفبایی مرتب میکنیم. مثلاً هشت رشتهی اول عبارتاند از: a,b,aa,ab,ba,bb,aaa,aab. رشتهی ۱۳۸۱ام کدام است؟
پاسخ
گزینه (۱) درست است.
معلوم است که تعداد رشتههای به طول i برابر2i میباشد. بنابراین آخرین رشته ۹ حرفی که به صورت bbbbbbbbb میباشد رشته هزار و بیست و دوم میباشد زیرا:
2+4+8+16+32+64+128+256+512=1022
به تعداد 210 رشته ده حرفی میتوان ساخت که نصف آنها با حرف a و نصف دیگر با حرف b شروع میشوند و چون رشته ۱۳۸۱ ام به نصفه اول متعلق است٬ بنابراین آن رشته با حرف a شروع میشود. لازم به ذکر است که رشته مورد نظر سیصد و پنجاه و نهمین رشته ده حرف است٬ زیرا 1381−1022=359 در بین ۵۱۲ رشتهای که با a شروع میشوند ۲۵۶ تای اول آنها حرف دوم a و ۲۵۶ تای دیگر(که ۳۵۹ نیز به همین دسته متعلق است) حرف دوم b دارند(چون 359−256=103<128 ، بنابراین رشته مورد نظر به دسته اول تعلق دارد). اگر به همین ترتیب ادامه دهیم خواهیم داشت:
حرف اول=a 1381−1022=359<512⇒
حرف دوم=b 359>256⇒
حرف سوم=a 359−256=103<128⇒
حرف چهارم=b 103>64⇒
حرف پنجم=b 103−64=39>32⇒
حرف ششم=a 39−32=7<16⇒
حرف هفتم=a 7<8⇒
حرف هشتم=b 7>4⇒
حرف نهم=b 7−4=3>2⇒
حرف دهم=a 3−2=1<7⇒