المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوال ۲۱

سوال ۲۱

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

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

پاسخ

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


ابزار صفحه