دنباله‌های بیتی کیست؟ توضیح بده.
دنباله‌های بیتی یکی از مباحث موجود در "نظریه اعداد" و "ریاضیات گسسته" هستند که به دلیل ویژگی‌های منحصر به فردشان در تقسیم‌بندی اعداد حقیقی و کاربردهایشان در "الگوریتم‌ها" و "رمزنگاری" مورد توجه قرار گرفته‌اند. این دنباله‌ها با استفاده از یک عدد حقیقی مثبت formula_1 تعریف می‌شوند.به این ترتیب، دنباله بیتی مربوط به formula_2 به صورت زیر بیان می‌شود:formula_3به عنوان مثال، formula_4، اما ویژگی کلیدی دنباله‌های بیتی در ارتباط آن‌ها با قضیه ریلی نهفته است که به موجب آن دو دنباله بیتی مکمل یکدیگر می‌شوند و تمام اعداد صحیح مثبت را بدون هم‌پوشانی پوشش می‌دهند.قضیه ریلی (Rayleigh theorem).اگر formula_5 دو عدد گنگ باشند که formula_6 آنگاه دنباله‌های formula_7 و formula_8 مجموعه اعداد طبیعی formula_9 را افراز می‌کنند.اثبات قضیه.ابتدا برای عدد ۱ بررسی می‌کنیم:formula_10formula_11formula_12پس ثابت شد عدد ۱ عضو دقیقاً یکی از دو مجموعه formula_7 و formula_8 است.حال کافی است ثابت کنیم برای هر formula_15، مجموعه‌های formula_16 و formula_17 مجموعه formula_18 را افراز می‌کنند.برای این کار نیاز داریم تا اندازه مجموعه formula_16 را محاسبه کنیم.بزرگ‌ترین formula_20 که formula_21 عضو مجموعه بالا باشد را در نظر بگیرید. در این صورت خواهیم داشت:formula_22formula_23از دو عبارت بالا نتیجه می‌شود کهformula_24 و لذا formula_25.با توجه به گنگ بودن formula_26 و formula_27 داریم:formula_28formula_29با جمع دو نامساوی بالا:formula_30عبارت وسط اکیداً بین دو عدد طبیعی متوالی قرار گرفته است پس:formula_31اکنون حکمی را که به دنبال اثبات آن بودیم را به کمک استقراء قوی ثابت می‌کنیم.حالت پایه formula_32 را قبلاً بررسی کردیم.فرض کنیم برای هر formula_33 حکم برقرار باشد یعنی formula_34 و formula_35 مجموعه formula_36 را افراز کنند. داریم:formula_37که formula_38.با توجه به فرض formula_39 می‌تواند مقدار صفر یا یک را اختیار کند، اگر formula_40 حکم به‌سادگی نتیجه می‌شود.اگر formula_41 یعنی formula_42 و یعنی:formula_43ولی با جای‌گذاری مقدار formula_39 در رابطه‌ای که بالا به‌دست آوردیم داریم:formula_45که تناقض است پس formula_39 فقط می‌تواند مقدار صفر را اختیار کند و این اثبات حکم را به اتمام می‌رساند.از آن‌جایی که حکم را برای تمامی formula_47ها ثابت کردیم قضیه ریلی به‌طور خودکار نتیجه می‌شود.خواص.چند خاصیت دنباله‌های بیتی:formula_54.۴) برای هر formula_47 صحیح و formula_56 داریم formula_57.در این لحظه می‌توان چند پرسش کلی طرح کرد!- در چه صورت formula_58؟- در چه صورت formula_59؟- آیا عکس خاصیت ۳ برقرار است؟- آیا عکس خاصیت ۴ برقرار است؟بررسی پرسش آخر:formula_60formula_61پس:formula_62.قبل از بیان خاصیت آخر نیاز به تعریف چگالی است،برای formula_63، چگالی به شکل زیر تعریف می‌شود:formula_64می‌توان به رابطه formula_65 نیز اشاره کرد.حال برای دنباله بیتی دل‌خواه داریم:5) formula_66اثباتی دیگر برای قضیه ریلی.یکی از اثبات‌هایی که برای قضیه ریلی وجود دارد اثباتی است که از تابع جزء اعشاری (Fractional Part Function) و خواص آن کمک می‌گیرد.برای هر عدد حقیقی formula_67 این تابع به این شکل تعریف می‌شود:formula_68اثبات. چون formula_67 و formula_70 صحیح نیستند پس وجود داردformula_74بطوریکه:formula_75formula_76با جمع دو تساوی بالا خواهیم داشت:formula_77از فرض نتیجه می‌شود، عبارت وسط تساوی عددی صحیح است لذا سمت راست نیز باید چنین باشد که تنها امکان این است که formula_78. بنابراین لم ثابت می‌شود.قبلاً نشان دادیم که برای هر formula_47 طبیعی داریم:formula_80حال توجه کنید که formula_81 و formula_82 در شرایط لم صدق می‌کنند؛ لذا خواهیم داشت:formula_83پس:formula_84با استفاده از این تابع می‌توان فهمید که اگر formula_85 باشد، آنگاه formula_86 باید در چه شرطی صدق کند:formula_87با استفاده از تابع جزء اعشاری داریم:formula_88مشابهاً برای formula_8 این شرط نتیجه می‌شود.حال اگر formula_90، طبق شرطی که به‌دست آوردیم:formula_91توجه کنید که formula_92 و formula_93 در شرایط لم صدق می‌کنند. پس با جمع کردن طرفین دو نابرابری خواهیم داشت:formula_94که تناقض است. پس:formula_95بنابراین formula_7 و formula_8 مجموعه اعداد طبیعی را افراز می‌کنند.بازی ویتوف.بازی ویتوف (Wythoff's game) یک بازی دو نفره با قواعدی ساده و نتایجی شگفت‌انگیز است. این بازی که به افتخار ریاضی‌دان هلندی "ویلیم ویتوف" نام‌گذاری شده است، یکی از بهترین نمونه‌های ارتباط بین ریاضیات نظری و استراتژی در بازی‌ها است. در این بازی، دو دسته مهره وجود دارد. بازیکنان به نوبت بازی می‌کنند و در هر نوبت می‌توانند:هدف این است که تمام مهره‌ها از بازی خارج شوند، بازیکنی که این کار را انجام دهد برنده استتوصیفی معادل از بازی بعدها توسط ریاضی‌دان "Rufus Isaacs" معرفی شد که بازی روی یک صفحه شطرنجی انجام می‌شود، به این صورت که در ابتدا وزیر یا یک مهره روی صفحه قرار داده شده است حال بازیکنان به نوبت می‌توانند مهره یا وزیر را حرکت دهند که قوانین خودش را دارد:۱. به تعداد دلخواه خانه می‌توان به سمت چپ رفت۲. به تعداد دلخواه خانه می‌توان به سمت پایین رفت۳. یا به تعداد دلخواه به صورت قطری حرکت کندبرنده کسی است که بتواند مهره را به خانه گوشه چپ پایین ببردبرای معادل ساری کافیست روی این صفحه محورهای مختصات را سوار کنیم بطوریکه خانه برنده مختصاتی برابر formula_98 داشته باشد. حال مختصات اولیه وزیر که formula_99 است نشانگر تعداد دسته مهره‌های ما در صورت قبلی بازی است که به‌ترتیب به تعداد formula_86 و formula_101 مهره دارنداستراتژی بهینه.برای توضیح استراتژی با مدل دوم بازی کار می‌کنیم.همان‌طور که گفته شد هر موقعیت در این بازی را می‌توان با یک زوج مرتب صحیح formula_99 که در آن formula_103 است توصیف کرد که این جفت اعداد اندازه هر دو دسته مهره در موقعیت فعلی یا مختصات وزیر را نشان می‌دهد. استراتژی بازی حول دو نوع موقعیت می‌چرخد: موقعیت سرد و موقعیت گرم. در یک موقعیت سرد، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه بازنده خواهد بود، در حالی که در یک موقعیت گرم، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه برنده می‌شود. استراتژی بهینه در یک موقعیت گرم این است که وزیر را به هر موقعیت سردی که قابل دسترسی است، منتقل کند.طبقه‌بندی موقعیت‌ها به دو دسته سرد و گرم به صورت بازگشتی و با استفاده از سه قانون زیر انجام می‌شود:برای مثال در یک صفحه formula_105 خانه‌های سرد و گرم به این صورت هستند:ویتوف کشف کرد که موقعیت‌های سرد یک الگوی منظم را دنبال می‌کنند که با نسبت طلایی تعیین می‌شود. به‌طور مشخص، اگر formula_106 یک عدد طبیعی باشد، آنگاه:formula_107formula_108که در اینجا formula_109 نسبت طلایی است در این حالت، formula_110 و formula_111 دو موقعیت سرد formula_106-ام هستند.همچنین برای هر formula_106 داریم: formula_114این دو دنباله formula_115 و formula_116 دنباله‌های بیتی مرتبط با معادله زیر هستند:formula_117- formula_115: این دنباله موقعیت‌های سرد کوچک‌تر را توصیف می‌کند:formula_119- formula_116: این دنباله موقعیت‌های سرد بزرگ‌تر را توصیف می‌کند.formula_121همان‌طور که در همه دنباله‌های بیتی صادق است، این دو دنباله مکمل هستند؛ یعنی اگر یک عدد طبیعی در یکی از دنباله‌ها ظاهر شود، در دنباله دیگر ظاهر نخواهد شد. این ویژگی برای بازی ویتوف و استراتژی‌های آن بسیار مهم است، زیرا به تفکیک کامل موقعیت‌ها کمک می‌کند و نقش مهمی در تعیین حرکات برنده دارد.کاربرد در رمزنگاری.شرح کاربرد.دنباله‌های بیتی به دلیل خواص منحصر به فردشان، در رمزنگاری کاربردهای جالبی دارند. این دنباله‌ها دو ویژگی اساسی دارند که آن‌ها را برای کاربردهای رمزنگاری مناسب می‌کند:موقعیت‌های خاص در دنباله‌های بیتی می‌توانند به کدگذاری اطلاعات کمک کنند. برای نمونه، می‌توان حروف یا کلمات یک پیام را به مقادیر متناظر در دنباله‌های بیتی نگاشت کرد.الگوریتم‌های رمزنگاری مبتنی بر خواص ریاضی دنباله‌های بیتی، به دلیل ساختار منظم اما غیرقابل پیش‌بینی، در برابر حملات مقاومت بالایی دارند.مثال عملی.گام‌های رمزنگاری.برای تولید دنباله بیتی از عدد گنگ formula_122 استفاده می‌کنیم؛ لذا فرمول تولید کلید برای هر formula_123 طبیعی برابراست با: formula_124.برای formula_125 کلید تولید شده عبارت است از:formula_126این بردار را تا طول پیام ادامه می‌دهیم.پیام: To: Logistics Command, Shipment of ammunition and medical supplies delayed by 12 hours. Adjust plans accordingly. Expect new delivery at 1800 hours. Heil Hitlerحال به حروف A تا Z اعداد ۰ تا ۲۵ را نسبت می‌دهیم اگر در متن، عدد وجود داشت آن را هم به صورت متن می‌نویسیم مثلاً در پیام بالا عدد ۱۲ وجود دارد، جای آن را با کلمه twelve عوض می‌کنیم.بدون در نطر گرفتن علائم نگارشی پیام تبدیل به بردار زیر می‌شود: P=[۱۹٬۱۴٬۱۱٬۱۴٬۶٬۸...]برای به‌دست آوردن بردار متن کدگذاری شده یعنی formula_127، به این صورت عمل می‌کنیم: formula_128لذا formula_127 می‌شود: D=[۲۳ ۱۰ ۰ ۲۱ ۶ ۰ ۳ ۲۲ ۳ ۱۶ ۲۴ ۱ ۵ ۲۲ ۱۴ ۲۰ ۰ ۸ ۱۶ ۲۳ ۱۷ ۱۶ ۵ ۱۶ ۱۷ ۱۶ ۳ ۱۳ ۰ ۴ ۲۳ ۲۳ ۹ ۲۲ ۰ ۷ ۵ ۲۳ ۲ ۸ ۱۶ ۱۸ ۲ ۱۹ ۱۷ ۳ ۲۰ ۲۳ ۲۳ ۱۷ ۴ ۲۳ ۱۱ ۱ ۱۵ ۲۲ ۲۵ ۱۸ ۱۸ ۲۵ ۱۶ ۱۴ ۶ ۲۲ ۱۱ ۲۵ ۲۰ ۲۱ ۲۰ ۲۳ ۲۴ ۱۹ ۱۹ ۱۷ ۷ ۰ ۱ ۲۲ ۲۰ ۲۴ ۱۴ ۸ ۲۲ ۱۱ ۱۸ ۲۳ ۲۱ ۲۱ ۱۶ ۸ ۱۳ ۸ ۱۲ ۱۰ ۷ ۱۹ ۱۶ ۲۲ ۲۰ ۵ ۱۶ ۲۳ ۱۴ ۲۳ ۱۰ ۱۹ ۳ ۳ ۲۲ ۲۲ ۱۱ ۱۷ ۱۸ ۲۳ ۲۳ ۱۷ ۳ ۱۶ ۸ ۱۷ ۲۴ ۵ ۴ ۳ ۱۹ ۲۰ ۲۵ ۷ ۱ ۲۳ ۱۴ ۷ ۱۲ ۱۸ ۲۳ ۹ ۱۷ ۲۴ ۳ ۲۱ ۱۷ ۱۶ ۱۵ ۴ ۲۴ ۵ ۲۱ ۱۷ ۱۲ ۱ ۲۰ ۲۴ ۸ ۲۰ ۲۵]پس از اعمال شیفت، بردار D را به حروف برمی‌گردانیم و متن کدگذاری‌شده را ۵ تا ۵ برش می‌زنیم، خواهیم داشت: XKAVG ADWDQ YBFWO UAIQX RQFQR QDNAE XXJWA HFXCI QSCTR DUXXR EXLBP WZSSZ QOGWL ZUVUX YTTRH ABWUY OIWLS XVVQI NIMKH TQWUF QXOXK TDDWW LRSXX RDQIR YFEDT UZHBX OHMSX JRYDV RQPEY FVRMB UYIUZرمزگشایی.برای رمزگشایی، همان عملیات شیفت را خلاف اعمال می‌کنیم یعنی برای به‌دست آوردن متن اصلی P داریم: formula_130متن اصلی بدون تغییر بازیابی می‌شود.تاریخچه.دنباله‌های بیتی (Beatty sequences) نام خود را از مسئله‌ای گرفته‌اند که در سال ۱۹۲۶ توسط ساموئل بیتی در مجله The American Mathematical Monthly مطرح شد. این مسئله احتمالاً یکی از پرارجاع‌ترین مسائلی است که تاکنون در این مجله مطرح شده است. با این حال، حتی پیش از آن، در سال ۱۸۹۴، چنین دنباله‌هایی به‌طور مختصر توسط لرد ریلی (Lord Rayleigh) در ویرایش دوم کتاب The Theory of Sound ذکر شده بودند.مطالعه بیش‌تر.چند منبع مرتبط با این دنباله‌ها معرفی می‌شود:این مقاله در arXiv موجود است و به بررسی دنباله‌های بیتی برای اعداد گنگ درجه دوم می‌پردازد.