Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۵

می‌دانیم که عدد nام فیبوناچی٬ یا Fn به این صورت تعریف می‌شود: F۰=۰٬ F۱=1 و Fn=Fn۱+Fn۲ برای ۲n. برای چه تعداد ۰n۱۰۰ عدد Fn بر ۱۳ بخش‌پذیر است؟

  1. ۹
  2. ۱۱
  3. ۱۳
  4. ۱۵
  5. ۱۷

پاسخ

گزینه (۴) درست است.

می‌دانیم باقی‌مانده مجموع دو عدد در تقسیم بر ۱۳(یا هر عدد دیگری) با باقی‌مانده مجموع باقی‌مانده‌های آن دو عدد در تقسیم بر ۱۳ برابر است. بنابراین باقی‌ماندهFi به ازای i از ۱ تا ۱۰۰ در تقسیم بر ۱۳ مطابق جدول زیر خواهد بود که دوره تناوبی برابر ۲۸ دارد. همان‌طور که مشاهده می‌شود تعداد مضارب ۱۳ در بین آن اعداد برابر [1007+1] یا ۱۵ می‌باشد.


ابزار صفحه