دورهمی طرح و حل مساله ریاضی/دنباله بیتی و خواص آن

راوی: محمد ابراهیمی و سید احمدالمهدی عالم زاده

راجع به این موضوع در دو جلسه صحبت شد: سه‌شنبه، ۲۰ شهریور ۱۴۰۳ و یک‌شنبه، ۲۵ شهریور ۱۴۰۳

گزارشی از مطالب کلاس

تعریف

دنباله‌های بیتی (Beatty Sequences) یکی از مباحث جذاب در نظریه اعداد و ریاضیات گسسته هستند که به دلیل ویژگی‌های منحصر به فردشان در تقسیم‌بندی اعداد حقیقی و کاربردهایشان در الگوریتم‌ها و رمزنگاری مورد توجه قرار گرفته‌اند. این دنباله‌ها با استفاده از یک عدد حقیقی مثبت $r\ge 1$ تعریف می‌شوند.

به این ترتیب، دنباله بیتی مربوط به $r$ به صورت زیر بیان می‌شود:

$A_r=\{\lfloor nr\rfloor :n\in \mathbb{N}\}$

به عنوان مثال، $A_1=\mathbb{N}$، اما ویژگی کلیدی دنباله‌های بیتی در ارتباط آن‌ها با قضیه ریلی نهفته است که به موجب آن دو دنباله بیتی مکمل یکدیگر می‌شوند و تمام اعداد صحیح مثبت را بدون هم‌پوشانی پوشش می‌دهند.

قضیه ریلی (Rayleigh theorem)

اگر $\alpha ,\beta >1$ دو عدد گنگ باشند که $\frac{1}{\alpha }+\frac{1}{\beta }=1$ آنگاه دنباله‌های $A_{\alpha }$ و $A_{\beta }$ مجموعه اعداد طبیعی $\mathbb{N}$ را افراز می‌کنند.

اثبات قضیه

ابتدا برای عدد ۱ بررسی می‌کنیم:

$1\in A_{\alpha }⟺1=\lfloor \alpha \rfloor ⟺1<\alpha <2$

$1\in A_{\beta }⟺1=\lfloor \beta \rfloor ⟺1<\beta <2$

$\frac{1}{\alpha }+\frac{1}{\beta }=1,(\alpha ,\beta \ne 2)⟹\min (\alpha ,\beta )<2<\max (\alpha ,\beta )$

پس ثابت شد عدد ۱ عضو دقیقاً یکی از دو مجموعه $A_{\alpha }$ و $A_{\beta }$ است.

حال کافی است ثابت کنیم برای هر $m\in \mathbb{N}$، مجموعه‌های $A_{\alpha }\cap \{1,\cdots ,m\}$ و $A_{\beta }\cap \{1,\cdots ,m\}$ مجموعه $\{1,\cdots ,m\}$ را افراز می‌کنند.

برای این کار نیاز داریم تا اندازه مجموعه $A_{\alpha }\cap \{1,\cdots ,m\}$ را محاسبه کنیم. بزرگ‌ترین $n\in \mathbb{N}$ که $\lfloor n\alpha \rfloor$ عضو مجموعه بالا باشد را در نظر بگیرید. در این صورت خواهیم داشت:

$n\alpha <m+1$

$(n+1)\alpha >m+1$

از دو عبارت بالا نتیجه می‌شود که$n=\lfloor \frac{m+1}{\alpha }\rfloor$ و لذا $|A_{\alpha }\cap \{1,\cdots ,m\}|=\lfloor \frac{m+1}{\alpha }\rfloor$.

با توجه به گنگ بودن $\alpha$ و $\beta$ داریم:

$\frac{m+1}{\alpha }-1<\lfloor \frac{m+1}{\alpha }\rfloor <\frac{m+1}{\alpha }$

$\frac{m+1}{\beta }-1<\lfloor \frac{m+1}{\beta }\rfloor <\frac{m+1}{\beta }$

با جمع دو نامساوی بالا:

$(m+1)(\frac{1}{\alpha }+\frac{1}{\beta })-2=m-1<\lfloor \frac{m+1}{\alpha }\rfloor +\lfloor \frac{m+1}{\beta }\rfloor <(m+1)(\frac{1}{\alpha }+\frac{1}{\beta })=m+1$

عبارت وسط اکیداً بین دو عدد طبیعی متوالی قرار گرفته است پس:

$\lfloor \frac{m+1}{\alpha }\rfloor +\lfloor \frac{m+1}{\beta }\rfloor =m$

اکنون حکمی را که به دنبال اثبات آن بودیم را به کمک استقراء قوی ثابت می‌کنیم. حالت پایه $m=1$ را قبلاً بررسی کردیم. فرض کنیم برای هر $k<m+1$ حکم برقرار باشد یعنی $A_{\alpha }\cap \{1,\cdots ,k\}$ و $A_{\beta }\cap \{1,\cdots ,k\}$ مجموعه $\{1,\cdots ,k\}$ را افراز کنند. داریم:

$|(A_{\alpha }\cap \{1,\cdots ,m+1\})\cup (A_{\beta }\cap \{1,\cdots ,m+1\})|=\lfloor \frac{m+2}{\alpha }\rfloor +\lfloor \frac{m+2}{\beta }\rfloor -s=m+1-s$

که $s=|A_{\alpha }\cap A_{\beta }\cap \{1,\cdots ,m+1\}|$.

با توجه به فرض $s$ می‌تواند مقدار صفر یا یک را اختیار کند، اگر $s=0$ حکم به‌سادگی نتیجه می‌شود. اگر $s=1$ یعنی $m+1\in A_{\alpha }\cap A_{\beta }\cap \{1,\cdots ,m+1\}$ و یعنی:

$|(A_{\alpha }\cap \{1,\cdots ,m+1\})\cup (A_{\beta }\cap \{1,\cdots ,m+1\})|=m+1$

ولی با جای‌گذاری مقدار $s$ در رابطه‌ای که بالا بدست آوردیم داریم:

$|(A_{\alpha }\cap \{1,\cdots ,m+1\})\cup (A_{\beta }\cap \{1,\cdots ,m+1\})|=m$

که تناقض است پس $s$ فقط می‌تواند مقدار صفر را اختیار کند و این اثبات حکم را به اتمام می‌رساند. از آن‌جایی که حکم را برای تمامی $m$ها ثابت کردیم قضیه ریلی به طور حودکار نتیجه میشود.

خواص

چند خاصیت دنباله‌های بیتی:

۱) اگر $k,l\in \mathbb{Q}$ آنگاه $A_k\cap A_l=A_{[k,l]}\ne \varnothing$.

۲) اگر $\alpha$ گنگ و $s$ گویا باشد آنگاه $A_{\alpha }\cap A_s\ne \varnothing$.

۳) هرگاه $\alpha$ گنگ باشد: $A_{\alpha }^c=A_{\frac{\alpha }{\alpha -1}}$.

۴) برای هر $m$ صحیح و $\beta \in {\mathbb{Q}}^c$ داریم $A_{m\beta }\subseteq A_{\beta }$.

در این لحظه می‌توان چند پرسش کلی طرح کرد!

- در چه صورت $A_{\alpha }\cap A_{\beta }=\varnothing$؟

- در چه صورت $A_{\alpha }\cup A_{\beta }=\mathbb{N}$؟

- آیا عکس خاصیت ۳ برقرار است؟

- آیا عکس خاصیت ۴ برقرار است؟

بررسی پرسش آخر:

$A_{\beta }^c=A_{\frac{\beta }{\beta -1}}⟹A_{\frac{m\beta }{\beta -1}}\subseteq A_{\beta }^c⟹A_{\beta }\subseteq A_{\frac{m\beta }{\beta -1}}^c=A_{\gamma }$

$\frac{\beta -1}{m\beta }+\frac{1}{\gamma }=1⟹\gamma =\frac{m\beta }{(m-1)\beta +1}$

پس: $A_{\beta }\subseteq A_{\frac{m\beta }{(m-1)\beta +1}}$.

قبل از بیان خاصیت آخر نیاز به تعریف چگالی است، برای $A\subseteq \mathbb{N}$، چگالی به شکل زیر تعریف می‌شود:

$\rho (A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{|A\cap \{1,\cdots ,n\}|}{n}$

می‌توان به رابطه $\rho (A^C)=1-\rho (A)$ نیز اشاره کرد. حال برای دنباله بیتی دل‌خواه داریم:

5) $\rho (A_{\alpha })=\frac{1}{\alpha }$

مطالب تکمیلی

اثباتی دیگر برای قضیه ریلی

یکی از اثبات‌هایی که برای قضیه ریلی وجود دارد اثباتی است که از تابع جزء اعشاری (Fractional Part Function) و خواص آن کمک می‌گیرد.

برای هر عدد حقیقی $x$ این تابع به این شکل تعریف می‌شود: $f(x)=\{x\}=x-\lfloor x\rfloor$

• لم. اگر $x$ و $y$ دو عدد ناصحیح باشند بطوریکه جمع آن‌ها صحیح باشد آنگاه $f(x)+f(y)=1$

اثبات. چون $x$ و $y$ صحیح نیستند پس وجود دارد $0<ϵ,\delta <1$ بطوریکه:

$f(x)=x-\lfloor x\rfloor =ϵ$

$f(y)=y-\lfloor y\rfloor =\delta$

با جمع دو تساوی بالا خواهیم داشت: $f(x)+f(y)=x+y-(\lfloor x\rfloor +\lfloor y\rfloor )=ϵ+\delta$

از فرض نتیجه می‌شود، عبارت وسط تساوی عددی صحیح است لذا سمت راست نیز باید چنین باشد که تنها امکان این است که $ϵ+\delta =1$. بنابراین لم ثابت می‌شود.

قبلاً نشان دادیم که برای هر $m$ طبیعی داریم: $|A_{\alpha }\cap \{1,\dots ,m\}|=\lfloor \frac{m+1}{\alpha }\rfloor$

حال توجه کنید که $\frac{m+1}{\alpha }$ و $\frac{m+1}{\beta }$ در شرایط لم صدق می‌کنند. لذا خواهیم داشت: $f\left(\frac{m+1}{\alpha }\right)+f\left(\frac{m+1}{\beta }\right)=1⟹\lfloor \frac{m+1}{\alpha }\rfloor +\lfloor \frac{m+1}{\beta }\rfloor =m$

پس: $(A_{\alpha }\cap \{1,\dots ,m\})\cup (A_{\beta }\cap \{1,\dots ,m\})=\{1,\dots ,m\}$

با استفاده از این تابع می‌توان فهمید که اگر $x\in A_{\alpha }$ باشد، آنگاه $x$ باید در چه شرطی صدق کند: $x\in A_{\alpha }⟹\mathrm{\exists }n\in \mathbb{N}\text{s.t.}x=\lfloor n\alpha \rfloor ⟹\mathrm{\exists }0<\epsilon <1\text{s.t.}x=n\alpha -\epsilon ⟹\frac{-x}{\alpha }=-n+\frac{\epsilon }{\alpha }$

با استفاده از تابع جزء اعشاری داریم: $f\left(\frac{-x}{\alpha }\right)=\frac{\epsilon }{\alpha }⟹f\left(\frac{-x}{\alpha }\right)<\frac{1}{\alpha }$

مشابهاً برای $A_{\beta }$ این شرط نتیجه می‌شود.

حال اگر $z\in A_{\alpha }\cap A_{\beta }$، طبق شرطی که بدست آوردیم: $f\left(\frac{-z}{\alpha }\right)<\frac{1}{\alpha },f\left(\frac{-z}{\beta }\right)<\frac{1}{\beta }$

توجه کنید که $\frac{-z}{\alpha }$ و $\frac{-z}{\beta }$ در شرایط لم صدق می‌کنند. پس با جمع کردن طرفین دو نابرابری خواهیم داشت: $f\left(\frac{-z}{\alpha }\right)+f\left(\frac{-z}{\beta }\right)=1<\frac{1}{\alpha }+\frac{1}{\beta }=1$

که تناقض است. پس: $A_{\alpha }\cap A_{\beta }=\mathrm{\varnothing }$

بنابراین $A_{\alpha }$ و $A_{\beta }$ مجموعه اعداد طبیعی را افراز می‌کنند.

بازی ویتوف (Wythoff's game)

معرفی بازی

بازی ویتوف یک بازی دو نفره با قواعدی ساده و نتایجی شگفت‌انگیز است. این بازی که به افتخار ریاضی‌دان هلندی ویلیم ویتوف نام‌گذاری شده است، یکی از بهترین نمونه‌های ارتباط بین ریاضیات نظری و استراتژی در بازی‌ها است.

در این بازی، دو دسته مهره وجود دارد. بازیکنان به نوبت بازی می‌کنند و در هر نوبت می‌توانند:

1- از یکی از دسته‌ها هر تعداد دلخواه مهره بردارند.

2- با از هر دو دسته، تعداد برابری مهره بردارند.

هدف این است که تمام مهره‌ها از بازی خارج شوند، بازیکنی که این کار را انجام دهد برنده است

توصیفی معادل از بازی بعد‌ها توسط ریاضی‌دان Rufus Isaacs معرفی شد که بازی روی یک صفحه شطرنجی انجام می‌شود، به این صورت که در ابتدا وزیر یا یک مهره روی صفحه قرار داده شده است حال بازیکنان به نوبت می‌توانند مهره یا وزیر را حرکت دهند که قوانین خودش را دارد:

1) به تعداد دلخواه خانه می‌توان به سمت چپ رفت

2) به تعداد دلخواه خانه می‌توان به سمت پایین رفت

3) و یا به تعداد دلخواه به صورت قطری حرکت کند

برنده کسی است که بتواند مهره را به خانه گوشه چپ پایین ببرد

برای معادل ساری کافیست روی این صفحه محور های مختصات را سوار کنیم بطوریکه خانه برنده مختصاتی برابر $(0,0)$ داشته باشد. حال مختصات اولیه وزیر که $(x,y)$ است نشانگر تعداد دسته مهره‌های ما در صورت قبلی بازی است که به‌ترتیب به تعداد $x$ و $y$ مهره دارند

استراتژی بهینه

برای توضیح استراتژی با مدل دوم بازی کار می‌کنیم. همانطور که گفته شد هر موقعیت در این بازی را می‌توان با یک زوج مرتب صحیح $(x,y)$ که در آن $x\le y$ است توصیف کرد که این جفت اعداد اندازه هر دو دسته مهره در موقعبت فعلی یا مختصات وزیر را نشان میدهد. استراتژی بازی حول دو نوع موقعیت می‌چرخد: موقعیت سرد و موقعیت گرم. در یک موقعیت سرد، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه بازنده خواهد بود، در حالی که در یک موقعیت گرم، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه برنده می‌شود. استراتژی بهینه در یک موقعیت گرم این است که وزیر را به هر موقعیت سردی که قابل دسترسی است، منتقل کند.

طبقه‌بندی موقعیت‌ها به دو دسته سرد و گرم به صورت بازگشتی و با استفاده از سه قانون زیر انجام می‌شود:

• 1. موقعیت $(0,0)$ یک موقعیت سرد است.

• 2. هر موقعیتی که بتوان با یک حرکت از آن به یک موقعیت سرد رسید، یک موقعیت گرم است.

• 3. اگر هر حرکتی از یک موقعیت به یک موقعیت گرم منتهی شود، آن موقعیت سرد است.

برای مثال در یک صفحه

$9*9$

خانه های سرد و گرم به این صورت هستند:

ویتوف کشف کرد که موقعیت‌های سرد یک الگوی منظم را دنبال می‌کنند که با نسبت طلایی تعیین می‌شود. به طور مشخص، اگر $n$ یک عدد طبیعی باشد، آنگاه:

$x_n=\lfloor n\varphi \rfloor =\lfloor y_n\varphi \rfloor -y_n$

$y_n=\lfloor n{\varphi }^2\rfloor =\lceil x_n\varphi \rceil =x_n+n$

که در اینجا $\varphi$ نسبت طلایی است در این حالت، $(x_n,y_n)$ و $(y_n,x_n)$ دو موقعیت‌ سرد $n$-ام هستند.

همچنین برای هر $n$ داریم: $y_n-x_n=n$

این دو دنباله $x_n$ و $y_n$ دنباله‌های بیتی مرتبط با معادله زیر هستند:

$\frac{1}{\varphi }+\frac{1}{{\varphi }^2}=1$

- $x_n$: این دنباله موقعیت‌های سرد کوچک‌تر را توصیف می‌کند:

$1,3,4,6,8,9,11,12,14,16,17,19,21,22,24,25,27,29,...$

- $y_n$: این دنباله موقعیت‌های سرد بزرگ‌تر را توصیف می‌کند.

$2,5,7,10,13,15,18,20,23,26,28,31,34,36,39,41,44,47,...$

همان‌طور که در همه دنباله‌های بیتی صادق است، این دو دنباله مکمل هستند. یعنی اگر یک عدد طبیعی در یکی از دنباله‌ها ظاهر شود، در دنباله دیگر ظاهر نخواهد شد. این ویژگی برای بازی ویتوف و استراتژی‌های آن بسیار مهم است، زیرا به تفکیک کامل موقعیت‌ها کمک می‌کند و نقش مهمی در تعیین حرکات برنده دارد.

کاربرد در رمزنگاری

شرح کاریرد

دنباله‌های بیتی به دلیل خواص منحصر به فردشان، در رمزنگاری کاربردهای جالبی دارند. این دنباله‌ها دو ویژگی اساسی دارند که آن‌ها را برای کاربردهای رمزنگاری مناسب می‌کند:

• کدگذاری پیام‌ها:

موقعیت‌های خاص در دنباله‌های بیتی می‌توانند به کدگذاری اطلاعات کمک کنند. برای نمونه، می‌توان حروف یا کلمات یک پیام را به مقادیر متناظر در دنباله‌های بیتی نگاشت کرد.

• ایجاد الگوریتم‌های امن:

الگوریتم‌های رمزنگاری مبتنی بر خواص ریاضی دنباله‌های بیتی، به دلیل ساختار منظم اما غیرقابل پیش‌بینی، در برابر حملات مقاومت بالایی دارند.

مثال عملی

گام‌های رمزنگاری

• 1 - تولید کلید

برای تولید دنباله بیتی از عدد گنگ $r=\sqrt{2}\pi$ استفاده می‌کنیم. لذا فرمول تولید کلید برای هر $k$ طبیعی برابراست با: $C_k=\lfloor k\sqrt{2}\pi \rfloor$.

برای $k=1,2,3,...$ کلید تولید شده عبارت است از:

$(4,8,13,17,22,26,31,35,39,44,48,53,57,62,66,71,75,79,...)$

این بردار را تا طول پیام ادامه میدهیم.

• 2 - تبدیل متن به کد

پیام:

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 اعداد 0 تا 25 را نسبت می‌دهیم اگر در متن، عدد وجود داشت آن را هم به صورت متن می‌نویسیم مثلا در پیام بالا عدد 12 وحود دارد، جای آن را با کلمه twelve عوض میکنیم. بدون در نطر گرفتن علائم نگارشی پیام تبدیل به بردارد زیر می‌شود:

P=[19,14,11,14,6,8,...]

• 3 - اعمال شیفت

برای بدست آوردن بردار متن کدگزاری شده یعنی $D$، به این صورت عمل میکنیم: $D_k\equiv P_k+C_k(\mathrm{mod}26)$

لذا $D$ می‌شود:

D=[23 10 0 21 6 0 3 22 3 16 24 1 5 22 14 20 0 8 16 23 17 16 5 16 17 16 3 13 0 4 23 23 9 22 0 7 5 23 2 8 16 18 2 19 17 3 20 23 23 17 4 23 11 1 15 22 25 18 18 25 16 14 6 22 11 25 20 21 20 23 24 19 19 17 7 0 1 22 20 24 14 8 22 11 18 23 21 21 16 8 13 8 12 10 7 19 16 22 20 5 16 23 14 23 10 19 3 3 22 22 11 17 18 23 23 17 3 16 8 17 24 5 4 3 19 20 25 7 1 23 14 7 12 18 23 9 17 24 3 21 17 16 15 4 24 5 21 17 12 1 20 24 8 20 25]

• 4 - متن رمزنگاری‌شده

پس از اعمال شیفت، بردار D را به حروف بر‌می‌گردانیم و متن کدگذاری‌شده را 5 تا 5 برش می‌زنیم، خواهیم داشت:

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) داریم: $P_k\equiv D_k-C_k(\mathrm{mod}26)$

متن اصلی بدون تغییر بازیابی می‌شود.

تاریخچه

دنباله‌های بیتی (Beatty sequences) نام خود را از مسئله‌ای گرفته‌اند که در سال ۱۹۲۶ توسط ساموئل بیتی در مجله The American Mathematical Monthly مطرح شد. این مسئله احتمالاً یکی از پرارجاع‌ترین مسائلی است که تاکنون در این مجله مطرح شده است. با این حال، حتی پیش از آن، در سال ۱۸۹۴، چنین دنباله‌هایی به طور مختصر توسط لرد ریلی (Lord Rayleigh) در ویرایش دوم کتاب The Theory of Sound ذکر شده بودند.

مطالعه بیش‌تر

چند منبع مرتبط با این دنباله‌ها معرفی می‌شود:

۱) مقاله "Beatty Sequences for a Quadratic Irrational: Decidability and Applications": این مقاله در arXiv موجود است و به بررسی دنباله‌های بیتی برای اعداد گنگ درجه دوم می‌پردازد.

۲) مقاله "Beatty sequences and Wythoff sequences, generalized": این مقاله در The Fibonacci Quarterly منتشر شده و به تعمیم دنباله‌های بیتی و ویتوف می‌پردازد.

۳) مقاله "Beatty sequences and multiplicative number theory": این مقاله به ارتباط بین دنباله‌های بیتی و نظریه اعداد ضربی می‌پردازد.

۴) مقاله "Beatty Sequences, Fibonacci numbers, and the golden ratio": این مقاله به بررسی ارتباط بین دنباله‌های بیتی، اعداد فیبوناچی و نسبت طلایی می‌پردازد.

۵) صفحه ویکی‌پدیا درباره دنباله بیتی