Processing math: 10%

سوال ۱۹

مجموعه‌ی کلمات ‎۱‎ تا ‎۶‎ حرفی از حروفِ ‎a‎ و ‎b‎ را مانند کلمات لغت‌نامه مرتب می‌کنیم. ‎۷۹،‎امین کلمه در این مجموعه‌ی مرتب کدام است؟ برای روشن شدن مفهوم مرتب کردن کلمات، مجموعه‌ی مرتب کلمات ‎۱‎ تا ‎۳‎ حرفی به‌ترتیب از چپ‌به‌راست برابر است با:

a‎, ‎aa‎, ‎aaa‎, ‎aab‎, ‎ab‎, ‎aba‎, ‎abb‎, ‎b‎, ‎ba‎, ‎baa‎, ‎bab‎, ‎bb‎, ‎bba‎, ‎bbb

‎ که نهمین کلمه در آن ‎ba‎ است.

  1. baabba
  2. abaaaa
  3. baaabb
  4. baab
  5. bab

پاسخ

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

تعداد کلماتی که حرف اول آن‌ها برابر 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 می‌شود.