مجموعهی کلمات ۱ تا ۶ حرفی از حروفِ a و b را مانند کلمات لغتنامه مرتب میکنیم. ۷۹،امین کلمه در این مجموعهی مرتب کدام است؟ برای روشن شدن مفهوم مرتب کردن کلمات، مجموعهی مرتب کلمات ۱ تا ۳ حرفی بهترتیب از چپبهراست برابر است با:
a, aa, aaa, aab, ab, aba, abb, b, ba, baa, bab, bb, bba, bbb
که نهمین کلمه در آن ba است.
پاسخ
گزینه (۱) درست است.
تعداد کلماتی که حرف اول آنها برابر a است و یک حرفی٬ دو حرفی٬… و شش حرفی میباشند٬ به ترتیب برابر 2^5،2^4،2^3،2^2،2^1،2^0 میباشند که مجموع آنها برابر 2^6-1 یعنی ۶۳ میشود. پس از کلمهی شصت و چهارم به بعد همهی کلمات با b شروع میشوند. تعداد کلماتی که با ba شروع میشوند 2^5-1 یعنی ۳۱ میباشد٬ بنابراین از کلمهی شصتوپنجم تا کلمهی نودوپنجم از جمله کلمهی هفتادونهم با ba شروع میشوند. تعداد کلماتی که با baa شروع میشوند برابر 2^۴-1؛ یعنی ۱۵ میباشد٬ بنابراین از کلمهی شصتوششم تا کلمهی هشتادم٬ از جمله کلمهی هفتادونهم با baa شروع میشوند. باهمین استدلال معلوم میشود که کلمهی هفتادونهم کلمهی baabba میشود.