المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۱۳

کامران یک دستگاه عددشمار ساخته است که ۷ لامپ دارد. معنی روشن یا خاموش بودن لامپ $i$ام به ترتیب ۱ یا ۰ بودن رقم $i$ ام یک عدد ۷ رقمی در مبنای ۲ است. مثلاً اگر فقط لامپ سوم روشن باشد دستگاه عدد ۸ را نمایش می‌دهد. در ابتدا همه‌ی لامپ ها خاموش هستند. این دستگاه دکمه‌ای دارد که با فشار آن، عدد دستگاه یک واحد افزایش می‌یابد. کامران با ۶۴ بار فشار دادن دکمه عدد اولیه ی صفر را به ۶۴ تبدیل می‌کند. اگر $d_i$ برابر با تعداد دفعاتی باشد که لامپ $i$ام تغییر وضعیت داده است، برابر چه مقدار است؟

  1. ۱۲۹
  2. ۱۲۷
  3. ۶۱
  4. ۶۵
  5. ۶۴

پاسخ

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

هر بار که لامپ $i$ ام از ۰ به ۱ تبدیل می‌شود لامپ‌های سمت چپ آن تغییر نمی‌کنند ولی هرگاه آن لامپ از ۱ به ۰ تبدیل می‌شود لامپ $(i+1)$ ام تغییر وضعیت می‌دهد. بنابراین اگر لامپ $i$ ام٬ $2k$ بار تغییر وضعیت دهد($k$ بار آن از ۰ به ۱ و $k$ بار دیگر آن از ۱ به ۰ می‌باشد) آن‌گاه لامپ $(i+1)$ ام٬ $k$ بار تغییر وضعیت می‌دهد. معلوم است که لامپ اول ۶۴ بار تغییر وضعیت می‌دهد٬ بنابراین لامپ‌های دوم٬ سوم٬ … و هفتم به ترتیب ۲٬۴٬۸٬۱۶٬۳۲ و ۱ بار تغییر وضعیت خواهند داد.بنابراین:

$$\sum_{i=1}^{7} d_i=64+32+16+8+4+2+1=127$$


ابزار صفحه