Loading [MathJax]/jax/output/HTML-CSS/jax.js

سوال ۲۱

برای هر عدد صحیح غیر منفی n ، عدد an+1 از an بر اساس قانون زیر به‌دست می‌آید:

اگر آخرین رقم سمت راست عدد an از ۵ بیش‌تر باشد، an+1=9an. در غیر این صورت٬ رقم سمت راست an را کنار می‌گذاریم و ارقام باقی‌مانده نمایشگر an+1 است. اگر an+1 شامل هیچ رقمی نباشد. کار پایان می‌یابد. آیا به ازای هر a0 دلخواه این فرایند پایان‌پذیر است؟

پاسخ

اگر a0 یکی از اعداد یک رقمی باشد حکم واضح است. حال ثابت می‌کنیم اگر حکم برای اعداد از ۱ تا k برقرار باشد٬ برای k+1 نیز برقرار است. اگر رقم آخر عدد (k+1) کوچک‌تر یا مساوی با ۵ باشد با کنار گذاشتن آن رقم٬ عدد حاصل کوچک‌تر از(k+1) خواهد بود و طبق فرض ادامه‌ی فرایند پایان‌پذیر خواهد بود. و اما اگر رقم آخر عدد (k+1) بزرگ‌تر از ۵ باشد در این صورت 9(k+1) به یکی از ارقام ۳٬۲٬۱ و ۴ ختم خواهد شد که با کنار گذاشتن این رقم حاصل از k+1 کوچک‌تر خواهد بود و باز بنا به فرض این فرایند پایان‌پذیر خواهد بود.