سوالات المپیاد:مرحله ی اول:دوره ی ۱۴:سوال ۲۵
سوال ۲۵
می‌دانیم که عدد $n$ام فیبوناچی٬ یا $F_n$ به این صورت تعریف می‌شود: $F_۰ = ۰$٬ $F_۱ = 1$ و $F_n = F_{n-۱} + F{n-۲}$ برای $۲ \le n$. برای چه تعداد $۰ \le n \le ۱۰۰$ عدد $F_n$ بر ۱۳ بخش‌پذیر است؟
- ۹
- ۱۱
- ۱۳
- ۱۵
- ۱۷
پاسخ
گزینه (۴) درست است.
می‌دانیم باقی‌مانده مجموع دو عدد در تقسیم بر ۱۳(یا هر عدد دیگری) با باقی‌مانده مجموع باقی‌مانده‌های آن دو عدد در تقسیم بر ۱۳ برابر است. بنابراین باقی‌مانده$F_i$ به ازای $i$ از ۱ تا ۱۰۰ در تقسیم بر ۱۳ مطابق جدول زیر خواهد بود که دوره تناوبی برابر ۲۸ دارد. همان‌طور که مشاهده می‌شود تعداد مضارب ۱۳ در بین آن اعداد برابر $[\frac{100}{7}+1]$ یا ۱۵ می‌باشد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
