====== سوال ۱۹ ======

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


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

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

‎
  - $baabba$
  - $abaaaa$
  - $baaabb$
  - $baab$
  - $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$ می‌شود.



</پاسخ>
  * [[سوال ۲۰|سوال بعد]]
  * [[سوال ۱۸|سوال قبل]]