با فرض انکه اداره پست ، تمبرهای 5 تومانی و 9 تومانی چاپ کرده است ، نشان دهید که برای n>=35 هر نامه ای را می توان ، تنها با استفاده از تمبرهای 5 تومانی و 9 تومانی ، به ارزش n تومان تمبر زد؟ طریقه تحلیل ان چگونه است من در کتاب خواندم ولی متوجه نشدم .
با تشکر
چون گفته‌شده که برای n>=35 چنین چیزی درسته پس باید پایه استقرا رو از مقدار ۳۵ شروع کنید.
پایه استقرا: اگر نامه نیاز به ۳۵ تومن تمبر داشته باشه که کار خیلی ساده هستش. چرا؟ چون با ۷ تا تمبر ۵ تومنی میشه نامه رو ۳۵ تومن تمبر زد. پس پایه استقرا برقراه چون تونستیم با تمبرهای موجود، ۳۵ تومن تمبر بزنیم. در این حالت نمیشه از ترکیبی از تمبرهای ۵ و ۹ تومنی استفاده کرد چون مقدار ۳۵ به دسj نمی‌یاد.
فرض استقرا: فرض می‌کنیم که با استفاده از تمبرهای ۵ و ۹ تومنی یک نامه که نیاز به n تومن تمبر داره رو بتونیم تمبر بزنیم.
حکم استقرا: باید نشون بدیم که میشه نامه‌ای که به n+1 تومن تمبر نیاز داره رو فقط با تمبرهای ۵ و ۹ تومنی تمبر زد.
طبق فرض استقرا الان n تومن تمبر رو با استفاده ار تمبرهای ۵ و ۹ تومنی در اختیار داریم. دو حالت مختلف میتونه اتفاق بیفته:
۱) تو این n تومن تمبر حداقل یک تمبر ۹ تومنی هم وجود داره. در این حالت چون میدونیم که حداقل یک تمبر ۹ تومنی وجود داره میتونیم یک تمبر ۹ تومنی رو برداریم و به جاش ۲ تا تمبر ۵ تومنی قرار بدیم. از n تومن تمبر موجود ۹ تومن کم میشه و بعد ۱۰ تومن بهش اضافه میشه که باز میشه n+1 تومن تمبر.
۲) تمام این n تومن تمبر با استفاده از تمبرهای ۵ تومنی ایجاد شده باشه. در این حالت میشه گفت که ما حداقل ۷ تا تمبر ۵ تومنی داریم. چرا؟ چون مقدار n بزرگتر مساوی ۳۵ هستش و تمام تمبرها هم ۵ تومنی هستن. حالا میشه خیلی راحت ۷ تا تمبر ۵ تومنی رو برداشت و به جاش ۴ تا تمبر ۹ تومنی قرار داد. n تومن تمبر داشتیم که ۳۵ تومن ازش کم شد و ۳۶ تومن بهش اضافه شد که این میشه همون n+1 تومن تمبر.
تمام.