دورهمی طرح و حل مساله ریاضی/مبنای فیبوناتچی و بازی‌های مهره‌ای

راویان: محمد هادی یعقوبی، حسین عسکریان، محمد حسین رضا‌نژاد

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

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

سوال مطرح شده در کلاس این بود که:

ثابت کنید هر عدد طبیعی را می‌توان به صورت جمعی از اعداد فیبوناچی بدون تکرار غیر متوالی نوشت.

ثابت کنید این نمایش یکتا است.

تعریف دنباله فیبوناتچی

$$\left(F_n\right)=\{\begin{array}{cc}1& n=1\text{ or }n=2\\ F_{n-1}+F_{n-2}& n>2\end{array}$$

بحث های مطرح در کلاس درباره دنباله فیبوناتچی

$$2F_n=F_n+F_{n-1}+F_{n-2}=F_{n+1}+F_{n-2}$$ $\underset{n\to \mathrm{\infty }}{\lim }\frac{F(n+1)}{F(n)}=L$ می‌خواهیم L را به دست آوریم . از طرفی $$\frac{F_{n+1}}{F_n}=\frac{1}{\frac{F_n}{F_{n+1}}}=\frac{1}{\frac{F_n}{F_{n-1}+F_n}}$$ که نتیجه می‌دهد $$L=\frac{1}{(\frac{1}{(\frac{1}{(1+\frac{1}{L})})})}$$

که نتیجه می‌دهد $$L=1+\frac{1}{L}$$ یا همان $$L\times L-L-1=0$$

که جواب این معادله با توجه به مثبت بودن همان عدد طلایی است . $$(1+\sqrt{(}5))*(\frac{1}{2})$$

نتیجه دیگر :‌ $$F_{n-2}<F_{n-1}\to F_{n-2}+F_{n-1}<2F_{n-1}\to F_n<2F_{n-1}$$

یک شهود :‌ میدانیم که با دنباله

۱ و ۲ و ۴ و ۸ و ۱۶ و ...

می‌توان هر عدد طبیعی را افراز کرد که هیچ یک از اعداد تکرار نداشته باشند . این نمایش نیز یکتا است . حال همان طور که مشخص است نسبت دنباله nام به n-1ام ۲ است . بدیهی است اگر این نسبت کمتر باشد انگاه باز هم میتوان هر عدد طبیعی را با جمله های دنباله جدید نوشت چون تراکم انها بیشتر شده است .

در مسیله مورد نظر ما به این علت که از جمله های متوالی نمیتوانیم استفاده کنیم این نسبت به عدد طلایی تبدیل میشود . چون رادیکال دو کمتر از عدد طلایی است میتوان اعداد طبیعی را با جمله های این دنباله به طور غیر متوالی افراز کرد .

حل سوال :‌ اکنون میخواهیم به کمک استقرا به حل سوال بپردازیم . برای پایه ۱=n چون خود ۱ جزو اعداد فیبوناچی هست .

حال فرض میکنیم برای k از ۱ تا n حکم سوال اثبات شده باشد . یعنی برای تمام اعداد از ۱ تا n افرازی غیر متوالی و یکتا از اعداد فیبوناچی موجود است .

حال با این فرض میخواهیم برای k = n + 1 را نیز اثبات کنیم . دنباله افراز شده n را در نظر بگیرید a1 , a2 , a3 , ... , aj اکنون عدد ۱ به این دنبال اضافه شده است . یعنی a0 .ممکن است با اضافه شدن ۱ شرط متوالی نبودن و تکراری نبودن نقض شود . در صورتی که تکرار داشته باشیم میتوان به جای دو تا جمله ۱ یک دانه جمله ۲ در نظر گرفت . (‌خود ۲ نیز جزو دنباله فیبوناچی است )‌ . دقت کنید چون در فرض a1 , a2 متوالی نبودند دو تا ۲ نخوهیم داشت چون ۲ بلافاصله بعد از ۱ است .

حال دنباله جدید ما تنها یک جفت متوالی دارد و مابقی همگی غیر متوالی هستند . در هر مرحله میتوان به جای این دو جفت متوالی جمله ی بعد انها را در نظر گرفت و ان دو را حذف کرد یعنی :‌

a1 , a2 , .... aj , aj+1 , aj+2 , ... اگر aj و aj+1 دو عضو متوالی ما باشند میتوان ان دو حذف و جمعشان یعنی ai را نوشت . چون هر دو فیبوناچی هستند و متوالی جمعشان نیز فیبوناچی خواهد بود . دقت کنید که aj+1 , aj+2 متوالی نیستند و حداقل ۱ فاصله دارند . با نوشتن aiاکنون دوباره حداکثر یک جفت متوالی در دنباله خواهیم داشت. که اگر با همین ترتیب جلو برویم به جمله انتهایی میرسیم و این روند پایان میپذیرد .

راه حل دوم :‌ فرض کنید میخواهیم n را افراز کنیم . در هر مرحله بزرگترین عدد فیبوناچی که ممکن است را از ان حذف میکنیم . اگر این عدد fnبوده باشد عدد بعدی نمیتواند fn-1باشد زیرا در این صورت جمعشان اول باید کم میشد این در حالی است که فرض کردیم در هر مرحله بزرگترین عدد فیبوناچی ممکن را حذف میکنیم . اکنون با ادامه دادن این روند چون در اخر دو تا ۱ داریم به این نتیجه میرسیم که حتما تمام میشود . اگر عددی اضافه مانده باشد یعین در یکی از مراحل بزرگترین عدد ممکن را حذف نکرده ایم چون عددی برابر ۱ یا بزرگتر از ان باقی مانده است!‌

در ضمن این نمایش یکتاست چون در همان ابتدا بزرگترین مقدار ممکن را نظر میگریم . میتوان اینگونه نیز اثبات کرد . دو دنباله را در نظر بگیرید که n را افراز کرده اند . هر بار بزرگترین عضو مجموعه را در نظر بگیرید و حذف کنید . اگر جایی این بزرگترین عضو یکسان نباشد میتوان گفت اگر بزرگترین عدد ممکن از مجموعه دیگری را بسازیم از این بزگترین عضو کمتر است . مانند زیر که دیگر B از A کوچک تر خواهد بود .

$F_1{F}_2{F}_3{F}_4{F}_5\dots F_J{F}_{J+1}$

  1  0      0  0  0  0  0 :A
  0  1 ...  1  0  1  0  1 :B

مسئله دیگر

یک بازی مهره ای داریم که در یک ردیف بی انتها از چپ راست از خانه ها تعدادی مهره قرار گرفته است . و در هر خانه نیز تعدادی مهره است . دو حرکت میتوانیم انجام بدهیم :‌

حرکت اول

                      []  []  [o,o]  []  ->  [o]  []  [] [o]
                      n-2 n-1  n  n+1      n-2  n-1   n  n+1

حرکت دوم

                        []  [o]  [o]  ->  [o]  []  [] 
                        n  n+1 n+2       n    n+1 n+2

ثابت کنید که این بازی پایان پذیر است و حالت نهایی یکتاست .

راه حل سوال

در صورتی که خانه را از اولین خانه مهره $F_1$ در نظربگیریم و تا آخر شماره گزاری را انجام دهیم با توجه به حرکات موجود دقیقا شرایط دنباله فیبوناچی را داریم با این تفاوت که از سمت چپ محدودیت نداریم .

میتوان خانه هارا تا حدی خوبی به راست برد و سپس شماره گذاری کرد تا جایی که مطمین باشیم نمیتوان به خانه ۱ دسترسی داشت . حال ثابت میکنیم این روند پایان پذیر است. امتیاز کل را اینگونه تعریف میکنیم . جمع شماره های هر خانه +‌ تعداد مهره ها

در حرکت اول امتیاز از $2n+2$ به $2n-1+2$ کاهش می یابد . که ۲ تعداد مهره ها است . در حرکت دوم هم امتیاز از $2n+1+2$ به $n+2+1$. یکی از مهرها کم میشود

با توجه به اینکه امتیاز همواره مثبت است و هر بار یکی عدد صحیح کم میشود پس این عمل پایان پذیر خواهد بود .

در کل ایده اصلی این بود . حال میتوان برای هر خانه وزن ها و امتیاز های دیگری در نظر گرفت . مثلا وزن 2 به توان n ,...

اگر وزن هر خانه را $F_n$ یعتی همان دنباله فیبوناچی در نظر بگیریم انگاه با این عمل جمع کل هر مهره در امتیاز خانه همیشه برابر خواهد بود . از طرفی میدانستیم که این هر عددی طبیعی را میتوان به صورت جمعی از اعداد فیبوناچی غیر متوالی نوشت . پس میتوان ارایشی در نظر گرفت که در همگی مهره ها حداقل یکی فاصله دارند و در هیچ خانه ای نیز پیش از یک مهره تیست . در این حالت هیچ کدام از شرایط حرکات برقرار نیست و نمیتوانیم حرکتی کنیم و بازی به پایان رسیده است .

مطالب تکمیلی (فیبوناتچی)

نمایش ماتریسی دنباله

ماتریس فیبوناتچی یک روش کارآمد برای محاسبه اعداد فیبوناتچی است که به ویژه در الگوریتم‌های کامپیوتری کاربرد دارد. این روش بر اساس یک رابطه ماتریسی ساده استوار است.

$${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n=\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)$$

مزایای روش ماتریسی

سرعت محاسبه: برای مقادیر بزرگ n، روش ماتریسی به مراتب سریع‌تر از روش‌های بازگشتی یا تکراری است.

سادگی پیاده‌سازی: این روش به سادگی در برنامه‌های کامپیوتری پیاده‌سازی می‌شود.

کاربرد در الگوریتم‌های دیگر: این روش در بسیاری از الگوریتم‌های مرتبط با دنباله فیبوناتچی و نظریه اعداد کاربرد دارد.

کاربردها

الگوریتم‌های مرتب‌سازی: در برخی الگوریتم‌های مرتب‌سازی مانند مرتب‌سازی فیبوناتچی از این روش استفاده می‌شود.

گراف‌ها و درخت‌ها: در تحلیل برخی ساختارهای گراف و درخت از اعداد فیبوناتچی و این روش محاسباتی استفاده می‌شود.

رمزنگاری: در برخی الگوریتم‌های رمزنگاری از خواص اعداد فیبوناتچی بهره گرفته می‌شود.

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

خاصیت های دیگر دنباله

قضیه 1

$$\sum _{i=1}^n{F}_i^2=F_n{F}_{n+1}$$

اثبات قضیه 1

با استفاده از استقرا ثابت می شود. پایه استقرا برابر 1 است. فرض می کنیم حکم برای $n$ برقرار است. اکنون برای $n+1$ داریم: $$\sum _{i=1}^n{F}_i^2+{F_{n+1}}^2=F_{n+1}(F_n+F_{n+1})$$ $$\sum _{i=1}^{n+1}{F}_i^2=F_{n+1}{F}_{n+2}$$ به وضوح می توان دید که حکم برقرار است.

قضیه 2

$$2^{n-1}\le F_{n+1}\le 2^n$$

اثبات قضیه 2

با استفاده از استقرا ثابت می شود. پایه استقرا برابر 1 است. فرض می کنیم حکم برای کمتر از $n$ برقرار است. اکنون برای $n+1$ داریم:

$$F_{n+2}\le 2F_{n+1}\le 2^{n+1}$$

$$2F_n\le 2^n\le F_{n+2}$$

در نتیجه می توان گفت: $$2^n\le F_{n+2}\le 2^{n+1}$$

قضیه 3

$$\sum _{i=0}^{n-1}{F}_{2i+1}=F_{2n}$$

اثبات قضیه 3

با استفاده از استقرا ثابت می شود. پایه استقرا برابر 1 است. فرض می کنیم حکم برای کمتر از $n$ برقرار است. اکنون برای $n+1$ داریم: $$\sum _{i=0}^{n-1}{F}_{2i+1}+F_{2n+1}=F_{2n}+F_{2n+1}$$ $$\sum _{i=0}^n{F}_{2i+1}=F_{2n+2}$$

قضیه 4

$$\gcd (F_{a_1},F_{a_2},F_{a_3},\dots ,F_{a_n})=F_{\gcd (a_1,a_2,a_3,\dots ,a_n)}$$

اثبات قضیه 4

با استفاده از استقرا روی تعداد اعضای داخل $gcd$ حکم را ثابت می کنیم. پایه استقرا را برابر با $n=2$ قرار می دهیم. در نتیجه ابتدا باید ثابت کنیم: $$\gcd (F_n,F_m)=F_{\gcd (n,m)}$$

اثبات این قضیه به خواننده سپرده می شود.(راهنمایی: ابتدا این موضوع را روی $n$ و $n+1$ با استفاده از قضیه بزو بررسی کنید)

حال با توجه به این قضیه می توان فرض کرد که برای n درست است. یعنی: $$\gcd (F_{a_1},F_{a_2},F_{a_3},\dots ,F_{a_n})=F_{\gcd (a_1,a_2,a_3,\dots ,a_n)}$$ حال برای n+1 داریم: $$\gcd (F_{a_1},F_{a_2},F_{a_3},\dots ,F_{a_n},F_{a_{n+1}})=\gcd (F_{\gcd (a_1,a_2,a_3,\dots ,a_n)},F_{n+1})$$ که با توجه به اثبات پایه استقرا حکم برقرار است.

رشته فیبوناتچی

تعریف

رشته ای دودویی است که به صورت زیر تعریف می شود: $$\left(S_n\right)=\{\begin{array}{cc}0& n=0\\ 01& n=1\\ S_{n-1}{S}_{n-2}& n>1\end{array}$$

رشته های تولید شده به شکل زیر هستند:

$S_0$    0

$S_1$    01

$S_2$    010

$S_3$    01001

$S_4$    01001010

$S_5$    0100101001001

...

ویژگی

رقم nام آن برابر است با: $$2+\lfloor n\phi \rfloor -\lfloor (n+1)\phi \rfloor$$ که $\phi$ نسبت طلایی است.

مطالب تکمیلی (ناوردایی)

ناوردایی

تکنیک استفاده شده در سوال مهره ها به ناوردایی مشهور است. در این روش با در نظر گرفتن خاصیتی از سوال نشان می دهند که این خاصیت دارای دنباله ای ثابت است. این روش معمولا برای اثبات متناهی بودن حرکات و یا دنباله استفاده می شود. در ادامه به بررسی چند سوال ناوردایی می پردازیم:

سوال ۱

در زبان Ao-Ao فقط دو حرف وجود دارد: A و O. علاوه بر این، قوانین زیر در این زبان رعایت می‌شوند: اگر دو حرف کنار هم AO را از کلمه‌ای حذف کنید، کلمه‌ای به دست می‌آورید که معنی اش همان قبلی است. به همین ترتیب، اگر ترکیب‌های OA و AAOO را در هر جایی در کلمه‌ای بگنجانید معنایش عوض می‌شود. آیا می‌توانیم مطمئن باشیم که معنی کلمه‌های AOO و OAA یکسان است؟

راه حل سوال ۱

توجه کنید که در حذف یا اضافه کردن هر ترکیبی از حرف ها، تعداد Aها در این ترکیب با تعداد Oها برابر است. یعنی اینکه تفاضل Aها و تعداد Oها ناورداست. به طور مثال:

$$O\to OOA\to OAAOOOA\to OAOOA$$

در همه این کلمه ها تعداد Oها از تعداد Aها یکی بیشتر است. راه حل را پی میگیریم. تفاضل موردنظر در مورد کلمه AOO برابر ۱- و در مورد کلمه OAA برابر با ۱ است. بنابراین، نمی توانیم با استفاده از عمل های مجاز کلمه OAA را از کلمه AOO به دست بیاوریم، و نمی توانیم ادعا کنیم که این کلمه ها مترادف اند.

سوال ۲

عددهای ۱، ۲، ۳،... ، ۱۹ و ۲۰ را روی تخته سیاه نوشته‌ایم. می‌توانیم دو عدد دلخواه مانند a و b را پاک کنیم و به جای آن‌ها عدد جدید a + b - 1 را روی تخته بنویسیم. پس از ۱۹ بار تکرار این عمل چه عددی رو تخته سیاه می‌ماند؟

راه حل سوال ۲

به ازای هر گردایه ای از n عدد روی تخته سیاه فرض کنید X برابر با مجموع این عددها منهای n باشد. فرض کنید عددهای روی تخته سیاه را به طریقی که گفتیم تبدیل کرده ایم. مقدار X چه تغییری می کند؟ اگر مجموع همه عددها به جز a و b برابر با S باشد، پیش از تبدیل $$X=S+a+b-n$$ و پس از تبدیل $$X=S+(a+b-1)-(n-1)=S+a+b-n$$ و در نتیجه، مقدار X همواره یکسان است، یعنی ناورداست. در ابتدا (در مورد عددهای گفته شده در صورت مساله)، $$X=\sum _{i=1}^{20}i-20=190$$ بنابراین، پس از 19 بار انجام عمل گفته شده، وقتی که فقط یک عدد روی تخته سیاه باقی مانده است، X برابر با 190 است. یعنی عدد آخر، که برابرا با X + 1 است، برابر با 191 است.

سوال ۳

عددهای ۱، ۲، ۳،... ، ۱۹ و ۲۰ را روی تخته سیاه نوشته‌ایم. می‌توانیم دو عدد دلخواه مانند a و b را پاک کنیم و به جای آن‌ها عدد جدید a + b + ab را روی تخته بنویسیم. پس از ۱۹ بار تکرار این عمل چه عددی رو تخته سیاه می‌ماند؟

(راهنمایی: مقداری که از جمع کردن هر عدد با ۱ و ضرب کردن نتیجه‌ها به دست می‌آید ناورداست)

سوال ۴

در کشورهای دیلیا و دالیا واحد پول به ترتیب دیلر و دالر است. در دیلیا ۱ دیلر را با ۱۰ دالر عوض می‌کنند و در دالیا ۱ دالر را با ۱۰ دیلر. تاجری ۱ دیلر دارد و می‌تواند به هر دو کشور سفر کند و پول‌هایش را بدون اینکه هزینه‌ای بپردازد تبدیل کند. ثابت کنید او هرگز نمی‌تواند یک مقدار مساوی دیلر و دالر داشته باشد، مگر اینکه بخشی از پولش را خرج کند.

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

https://en.wikipedia.org/wiki/Fibonacci_sequence در این لینک نیز اطلاعات جذاب و بیشتری در مورد دنباله فیبونا چی موجود است. حتما یه نگاه کنید.

https://cs.uwaterloo.ca/journals/JIS/VOL22/Chu2/chu9.pdf

https://drops.dagstuhl.de/storage/00lipics/lipics-vol157-fun2021/LIPIcs.FUN.2021.16/LIPIcs.FUN.2021.16.pdf

https://www.fq.math.ca/Papers1/55-5/Allouche.pdf