======سوالات ۳۴ و ۳۵ ======

رشته‌ي $S_۰ = aAbBaAb$ را درنظر بگیرید. از روی این رشته می توانیم رشته‌ی $S_۱$ را با این قاعده بسازیم که به جای حرف $A$ عبارت $BaB$ و به جای هر $B$ عبارت $AbA$ را بگذاریم. با این وصف رشته‌ی $S_۱$ برابر با $aBaBbAbAaBaBb$ خواهد بود. با همین قاعده می توانیم رشته های $S_۲$ ٫ $S_۳$ و... را بسازیم.

با توجه به توضیحات بالا به دو سوال زیر پاسخ دهید:

======سوال ۳۴======

۷۷۷ اُمین حرف از سمت چپ در رشته‌ی $S_۷$ کدام است؟

  - $a$
  - اندازه‌ي رشته کمتر از ۷۷۷ است
  - $A$
  - $B$
  - $b$
<پاسخ>

گزینه‌ی «۲» درست است.



بیایید طول رشته را حساب کنیم. در $s_0$ما 3 تا حرف بزرگ داریم و هر دفعه به جای هر حرف بزرگ، 2 حرف بزرگ دیگر قرار می‌گیرد پس در $s_7$ ما $3\times27$ حرف بزرگ داریم. همچنین هر مرحله به اندازه حروف بزرگ به تعداد حروف کوچک اضافه می‌شود یا می‌توانیم بگوییم هر مرحله رشته‌ی ما یکی در میان حروف بزرگ و کوچک است، پس حروف کوچک تعدادشان یکی بیش‌تر از حروف بزرگ است، پس در کل $3\times2^8+1=769$حرف در $s_7$ داریم که این تعداد از 777 کم‌تر است!
</پاسخ>
======سوال ۳۵ ======

۱۰۲۷ اُمین حرف از سمت چپ در رشته‌ی $S_۹$ کدام است؟

  - اندازه‌ي رشته کمتر از ۱۰۲۷ است
  - $a$
  - $A$
  - $B$
  - $b$

<پاسخ>

گزینه‌ی «۵» درست است.

اﮔﺮ ﺗﻤﺎمی ﺣﺮوفی ﮐﻪ از اوﻟﯿﻦ $A$ (دوﻣﯿﻦ ﺣﺮف از ﺳﻤﺖ ﭼﭗ) در $S_٠$ ﺳﺎﺧﺘﻪ میﺷﻮﻧﺪ را ﻗﺮﻣﺰ ﮐﻨﯿﻢ (ﻫﻢ ﺣﺮوف
ﺳﺎﺧﺘﻪ ﺷﺪه ﺑﻪ ﺻﻮرت ﻣﺴﺘﻘﯿﻢ در $S_١$ و ﻫﻢ در اداﻣﻪ ﺣﺮوفی ﮐﻪ از اﯾﻦ ﺣﺮوف ﻗﺮﻣﺰ ﺳﺎﺧﺘﻪ میﺷﻮﻧﺪ)، ﺧﻮاﻫﯿﻢ دﯾﺪ
ﮐﻪ در $S_٩$ اﺑﺘﺪا ﯾک $a$  مشکی دارﯾﻢ ﮐﻪ از اﺑﺘﺪا دﺳﺖ ﻧﺨﻮرده ﻣﺎﻧﺪه اﺳﺖ، ﺳﭙﺲ ١٠٢٣ ﺣﺮف ﻗﺮﻣﺰ ﺑﺰرگ ﯾﺎ
ﮐﻮچک دارﯾﻢ (ﭼﺮا؟)، ﭘﺲ از آن ﯾک $b$  مشکی (دﺳﺖ ﻧﺨﻮرده از اﺑﺘﺪا) و ﭘﺲ از آن ﺣﺮوفی می‌آﯾﻨﺪ ﮐﻪ از $B$
ﻣﻮﺟﻮد در $S_٠$ ﺳﺎﺧﺘﻪ ﺷﺪه اﻧﺪ.


ﺑﺎ اﯾﻦ وﺻﻒ ﻣﺴﺌﻠﻪ ﺗﺒﺪﯾﻞ میﺷﻮد ﺑﻪ اﯾﻦ ﮐﻪ ٢=١٠٢٧-١-١٠٢٣-١ اُﻣﯿﻦ ﺣﺮف از ﺳﻤﺖ ﭼﭗ رﺷﺘﻪای ﮐﻪ از B ﭘﺲ از ٩ ﻣﺮﺣﻠﻪ ﺳﺎﺧﺘﻪ میﺷﻮد را ﺑﯿﺎﺑﯿﻢ. در روشی ﻣﺸﺎﺑﻪ، اﯾﻦ ﺑﺎر ﺣﺮوفی ﮐﻪ از اﯾﻦ Bی ﻣﻮﺟﻮد در $S_٠$
ﺑﻪ ﺻﻮرت ﻣﺴﺘﻘﯿﻢ ﯾﺎ ﻏﯿﺮﻣﺴﺘﻘﯿﻢ ﺳﺎﺧﺘﻪ میﺷﻮﻧﺪ را آﺑﯽ می ﮐﻨﯿﻢ. اﮐﻨﻮن ﮐﺎفی ﺳﺖ دوﻣﯿﻦ ﺣﺮف آﺑﯽ در $S_٩$ را
ﺑﯿﺎﺑﯿﻢ.


اﮔﺮ دﻗﺖ ﮐﻨﯿﻢ در اوﻟﯿﻦ ﻣﺮﺣﻠﻪ اﺟﺮای ﻗﺎﻋﺪه، رﺷﺘﻪ آﺑﯽ ﺑﺎ $Ab...$ ﺷﺮوع میﺷﻮد (در $S_١$)؛ ﻫﻤﯿﻦ ﻗﺴﻤﺖ در $S_٢$
رﺷﺘﻪای ﺑﻪ ﺻﻮرت $Ba...$ را  میﺳﺎزد. ﺑﺎ ﻫﻤﯿﻦ روﯾﻪ  میﺗﻮاﻧﯿﻢ ﺑﺒﯿﻨﯿﻢ رﺷﺘﻪی آﺑﯽ در $S_٩$ ﺑﺎ $Ab...$ ﺷﺮوع میﺷﻮد و در ﻧﺘﯿﺠﻪ دوﻣﯿﻦ ﺣﺮف آﺑﯽ و ١٠٢٧ اُﻣﯿﻦ ﺣﺮف ﮐﻞ رﺷﺘﻪ ی $S_٩$ ﺑﺮاﺑﺮ ﺑﺎ $b$ اﺳﺖ.

</پاسخ>
  * [[سوالات ۳۲ و ۳۳|سوال قبل]]