سلام خدمت همه ی دوستان عزیز

همانطور که دوست عزیزمون گفتن قسمت الف که راحته من قسمت ب رو اثبات می کنم.

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

من می گم به خونه ی $B_i$ عدد فیبوناچی $i$ام رو نسب می دهیم به جند رابطه ی زیر توجه داشته باشید.

$F_{i} + F_{i+1} = F_{i+2}$

$ 2F_i = F_{i-2} + F_{i-1} + F_i = F_{i-2} + F_{i+1} $

همانطور که در بالا می ببینید $Sum$ همواره ثابت می ماند.

پس در ابتدا:

$ Sum = \sum_{i=1}^n F_i $

حالا اگر بخواهیم کاری کنیم که در خانه ی $n+2$ام توپی باشد حداقل باید $ F_{n+2} \le Sum $ که اینرو ما با لم1رد می کنیم.

و حکم ثابت می شود.

لم1: $ F_n > \sum_{i=1}^{n-2} F_i $ به ازای $(n >1)$.

اثبات: با استقرا اثبات می کنیم.

_پایه استقرا: $n=2$ که داریم: $F_2 = 2 > F_0 = 1$

_فرض استقرا: حکم به ازای $n-1$ درست است.

_حکم استقر: آیا حکم به ازای $n$ درست است؟

$ \sum_{i=1}^{n-2} F_i = \sum_{i=1}^{n-3} F_i + F_{i-2} $$S=$

طبق فرض داریم:

$ \sum_{i=1}^{n-3} F_i < F_{n-1} $

پس:

$S < F_{i-1} +F_{i-2} = F_i$

$S < F_i$

و حکم اثبات می شود.

موفق و موئید باشید.

رویn استقرا قوی می زنیم: فرض:اگر جدول 1*(n+2) با n تا مهره داشته باشیم (مثل فرض)،هرگز نمیتوان مهره ای را به آخر جدول رساند. پایه برای n=1 بدیهه اثبات حکم برای n+1:اولین حرکتی که می کنیم حرکت نوع 1 است فرض کنید این حرکت روی خانه ی i انجام شود یعنی مهره ای از i به i+2 منتقل و از i+1 حذف شود.حال جدولی که از خانه ی i+1 تا n+3 است را درنطر بگیرید یک جدول (n+3-i) تایی با n+1-i تا مهره است که اگر n+i-1=t باشد tتا مهره با یک جدول t+2 خانه ای داریم . جدولی که از خانه ی 1 تا i+1 است یک جدول باویژگی فرض استقرا است پس از این جدول مهره ای به خانه ی i+1 نمی آید پس این تیکه رو حذف می کنیم.حال در جدول باقیمانده اگر هیچ حرکتی از نوع2 انجام نشود که بدیهتا به خانه آخر نمی رسیم در غیر اینصورت اولین حرکت از نوع 2 این جدول را به جدولی تبدیل می کند که می توان از جدول فرض استقرا به آن رسید و طبق فرض استقرا در این جدول نمی توان مهره ای در آخرین خانه گذاشت .