دستگاه عددساز در ابتدا عدد x را که برابر با صفر است نمایش میدهد. این دستگاه از ما یک دنباله از اعداد ۰ و ۱ میگیرد و طی مراحل زیر عدد x را تغییر میدهد:
با شروع از اولین عدد، به ازای هر عدد در دنباله:
یک دنباله از ۰ و ۱ را «معتبر» مینامیم اگر در آن هیچ سه عدد متوالی برابر با ۱ نباشند.
با استفاده از دستگاه عددساز و دنبالههای معتبر به طول ۵ چند عدد مختلف میتوان ساخت؟
راهنمایی
در سوال بعد آمده است
پاسخ
گزینهی ۱ درست است.
راه حل در سوال بعدی توضیح داده شده است.
با استفاده از دستگاه عددساز و دنبالههای معتبر به طول ۱۰ چند عدد مختلف میتوان ساخت؟
راهنمایی
اگر عدد حاصل از دو دنباله برابر باشد دو دنباله هم باهم برابرند
راهنمایی
روی آخرین صفر دنباله n عضوی حالت بندی کنید این صفر در چه جایگاه هایی می تواند باشد؟
پاسخ
گزینهی ۲ درست است.
نشان میدهیم اگر عدد حاصل از دو دنبالهی a و b با طول برابر یکسان باشد، a=b. آخرین ۰ دنباله را در نظر میگیریم. اگر بعد از آن ۱ای نیامده باشد رقم آخر x در مبنای چهار برابر ۰ است. در غیر این صورت یا یکبار عدد ۱ بعد از آن آمده که در نتیجه رقم آخر x در مبنای چهار، ۳ است و یا دوبار عدد ۱ آمده که رقم آخر x در مبنای چهار برابر با ۲ است. در هر صورت آخرین رقم x هرچه باشد یک یا دو یا سه عضو انتهای دنبالهی سازندهی آن یکتا تعیین میشود. با حذف این عناصر از انتهای a و b و محاسبهی مقدار x قبل از آنها دنبالهها کوچکتر میشوند و طبق فرض همچنان اعداد برابری تولید میکنند. با ادامهی این روند پایان پذیر برابری a=b ثابت میشود. پس مسئله به مسئلهی شمردن تعداد رشتههای معتبر به طول n تبدیل میشود.
F(n) را برابر با تعداد رشتههای معتبر به طول n در نظر میگیریم. میتوان نشان داد:
F(n)=F(n−1)+F(n−2)+F(n−3)
F(1)=2,F(2)=4,F(3)=7,F(4)=13,F(5)=24,...,F(10)=504
فرض کنید بتوانیم دنبالههای معتبر به هر طول دلخواهی را به دستگاه عددساز بدهیم. حداکثر چند عدد کوچکتر از ۲۰۴۸ میتوانیم بسازیم؟
راهنمایی
دنباله حتما باید با یک شروع شود و حداکثر چند صفر داشته باشد؟ بعد از هر صفر چه حالت هایی برای یک های بعد آن صفر تا صفر بعدی داریم؟
پاسخ
گزینهی ۴ درست است.
با کنار گذاشتن حالت x=0، میتوانیم از ۰ های اول دنباله صرفنظر کنیم (چون x را تغییر نمیدهند). پس دنباله با ۱ شروع میشود و حداکثر چهار ۰ بعد از آن داریم. زیرا در غیر این صورت عدد x دستکم برابر با 3×45=3072 میشود. با این حساب بیشترین عدد x با دنبالهی [1,1,0,1,1,0,1,1,0,1,1,0,1,1] تولید میشود که برابر با ۲۰۴۶ است. تعداد ۱های موجود بعد از هر ۰ در دنباله میتواند عددی بین صفر تا دو باشد و دنباله با یک یا دو عدد ۱ آغاز خواهد شد. پس اگر iتا ۰ در دنباله داشته باشیم 2×3i حالت مختلف خواهیم داشت.تعداد ۰ها در دنباله پنج حالت دارد (0≤i≤4) در نتیجه پاسخ سوال برابر است با: 1+4∑i=02×3i=1+2×(30+31+32+33+34)=243