موضوع مقاله: دنباله‌های بیتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # دنباله‌های بیتی | مقدمه: دنباله‌های بیتی یکی از مباحث موجود در نظریه اعداد و ریاضیات گسسته هستند که به دلیل ویژگی‌های منحصر به فردشان در تقسیم‌بندی اعداد حقیقی و کاربردهایشان در الگوریتم‌ها و رمزنگاری مورد توجه قرار گرفته‌اند. | ## بخش 1: دنباله‌های بیتی | به این ترتیب، دنباله بیتی مربوط به به صورت زیر بیان می‌شود: به عنوان مثال، ، اما ویژگی کلیدی دنباله‌های بیتی در ارتباط آن‌ها با قضیه ریلی نهفته است که به موجب آن دو دنباله بیتی مکمل یکدیگر می‌شوند و تمام اعداد صحیح مثبت را بدون هم‌پوشانی پوشش می‌دهند. اثبات قضیه ابتدا برای عدد ۱ بررسی می‌کنیم: پس ثابت شد عدد ۱ عضو دقیقاً یکی از دو مجموعه و است. با توجه به گنگ بودن و داریم: با جمع دو نامساوی بالا: عبارت وسط اکیداً بین دو عدد طبیعی متوالی قرار گرفته است پس: اکنون حکمی را که به دنبال اثبات آن بودیم را به کمک استقراء قوی ثابت می‌کنیم. با توجه به فرض می‌تواند مقدار صفر یا یک را اختیار کند، اگر حکم به‌سادگی نتیجه می‌شود. اگر یعنی و یعنی: ولی با جای‌گذاری مقدار در رابطه‌ای که بالا به‌دست آوردیم داریم: که تناقض است پس فقط می‌تواند مقدار صفر را اختیار کند و این اثبات حکم را به اتمام می‌رساند. از آن‌جایی که حکم را برای تمامی ها ثابت کردیم قضیه ریلی به‌طور خودکار نتیجه می‌شود. قبل از بیان خاصیت آخر نیاز به تعریف چگالی است، برای ، چگالی به شکل زیر تعریف می‌شود: می‌توان به رابطه نیز اشاره کرد. چون و صحیح نیستند پس وجود دارد بطوریکه: با جمع دو تساوی بالا خواهیم داشت: از فرض نتیجه می‌شود، عبارت وسط تساوی عددی صحیح است لذا سمت راست نیز باید چنین باشد که تنها امکان این است که . قبلاً نشان دادیم که برای هر طبیعی داریم: حال توجه کنید که و در شرایط لم صدق می‌کنند؛ لذا خواهیم داشت: پس: با استفاده از این تابع می‌توان فهمید که اگر باشد، آنگاه باید در چه شرطی صدق کند: با استفاده از تابع جزء اعشاری داریم: مشابهاً برای این شرط نتیجه می‌شود. این بازی که به افتخار ریاضی‌دان هلندی ویلیم ویتوف نام‌گذاری شده است، یکی از بهترین نمونه‌های ارتباط بین ریاضیات نظری و استراتژی در بازی‌ها است. | ## بخش 2: دنباله‌های بیتی | بازیکنان به نوبت بازی می‌کنند و در هر نوبت می‌توانند: از یکی از دسته‌ها هر تعداد دلخواه مهره بردارند. هدف این است که تمام مهره‌ها از بازی خارج شوند، بازیکنی که این کار را انجام دهد برنده است توصیفی معادل از بازی بعدها توسط ریاضی‌دان Rufus Isaacs معرفی شد که بازی روی یک صفحه شطرنجی انجام می‌شود، به این صورت که در ابتدا وزیر یا یک مهره روی صفحه قرار داده شده است حال بازیکنان به نوبت می‌توانند مهره یا وزیر را حرکت دهند که قوانین خودش را دارد: بی‌قاب|راست ۱. یا به تعداد دلخواه به صورت قطری حرکت کند برنده کسی است که بتواند مهره را به خانه گوشه چپ پایین ببرد برای معادل ساری کافیست روی این صفحه محورهای مختصات را سوار کنیم بطوریکه خانه برنده مختصاتی برابر داشته باشد. حال مختصات اولیه وزیر که است نشانگر تعداد دسته مهره‌های ما در صورت قبلی بازی است که به‌ترتیب به تعداد و مهره دارند استراتژی بهینه برای توضیح استراتژی با مدل دوم بازی کار می‌کنیم. همان‌طور که گفته شد هر موقعیت در این بازی را می‌توان با یک زوج مرتب صحیح که در آن است توصیف کرد که این جفت اعداد اندازه هر دو دسته مهره در موقعیت فعلی یا مختصات وزیر را نشان می‌دهد. در یک موقعیت سرد، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه بازنده خواهد بود، در حالی که در یک موقعیت گرم، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه برنده می‌شود. استراتژی بهینه در یک موقعیت گرم این است که وزیر را به هر موقعیت سردی که قابل دسترسی است، منتقل کند. طبقه‌بندی موقعیت‌ها به دو دسته سرد و گرم به صورت بازگشتی و با استفاده از سه قانون زیر انجام می‌شود: ۱. برای مثال در یک صفحه خانه‌های سرد و گرم به این صورت هستند:بی‌قاب|وسط|250px ویتوف کشف کرد که موقعیت‌های سرد یک الگوی منظم را دنبال می‌کنند که با نسبت طلایی تعیین می‌شود. به‌طور مشخص، اگر یک عدد طبیعی باشد، آنگاه: که در اینجا نسبت طلایی است در این حالت، و دو موقعیت سرد -ام هستند. | ## بخش 3: دنباله‌های بیتی | همچنین برای هر داریم: این دو دنباله و دنباله‌های بیتی مرتبط با معادله زیر هستند: - : این دنباله موقعیت‌های سرد کوچک‌تر را توصیف می‌کند: - : این دنباله موقعیت‌های سرد بزرگ‌تر را توصیف می‌کند. همان‌طور که در همه دنباله‌های بیتی صادق است، این دو دنباله مکمل هستند؛ یعنی اگر یک عدد طبیعی در یکی از دنباله‌ها ظاهر شود، در دنباله دیگر ظاهر نخواهد شد. این ویژگی برای بازی ویتوف و استراتژی‌های آن بسیار مهم است، زیرا به تفکیک کامل موقعیت‌ها کمک می‌کند و نقش مهمی در تعیین حرکات برنده دارد. کاربرد در رمزنگاری شرح کاربرد دنباله‌های بیتی به دلیل خواص منحصر به فردشان، در رمزنگاری کاربردهای جالبی دارند. این دنباله‌ها دو ویژگی اساسی دارند که آن‌ها را برای کاربردهای رمزنگاری مناسب می‌کند: رمزنگاری پیام‌ها: موقعیت‌های خاص در دنباله‌های بیتی می‌توانند به کدگذاری اطلاعات کمک کنند. برای نمونه، می‌توان حروف یا کلمات یک پیام را به مقادیر متناظر در دنباله‌های بیتی نگاشت کرد. ایجاد الگوریتم‌های امن: الگوریتم‌های رمزنگاری مبتنی بر خواص ریاضی دنباله‌های بیتی، به دلیل ساختار منظم اما غیرقابل پیش‌بینی، در برابر حملات مقاومت بالایی دارند. مثال عملی گام‌های رمزنگاری ۱ - تولید کلید برای تولید دنباله بیتی از عدد گنگ استفاده می‌کنیم؛ لذا فرمول تولید کلید برای هر طبیعی برابراست با: . | ## جمع‌بندی | این مسئله احتمالاً یکی از پرارجاع‌ترین مسائلی است که تاکنون در این مجله مطرح شده است.