======سوال ۱۳======

روی یک دستگاه $n$ عدد کلید و یک نمایشگر قرار دارد. در ابتدا هرکدام از کلیدها یا روشن است یا خاموش و نمایشگر همیشه تعداد کلیدهای روشن را نشان می‌دهد. ما از وضعیت روشن یا خاموش بودن کلیدها اطلاع نداریم و در هر مرحله تنها می‌توانیم یک کلید دلخواه را تغییر وضعیت دهیم. حداکثر در طی چند مرحله می‌توانیم تمام کلیدها را روشن کنیم؟

  - $n-۱$
  - $n$
  - $۲n-۱$
  - $۲n$
  - $۲n+۱$
<پاسخ>
گزینه‌ی (۳) درست است.


اگر با فشردن یک کلید عدد نمایشگر زیاد شد، یعنی لامپ آن خاموش بوده و حالا روشن است و نیازی به فشردن دوباره‌ی آن کلید نیست و اگر عدد کم شد باید یک بار دیگر آن را فشار دهیم. بنابراین اگر $x$ چراغ خاموش داشته باشیم، به ازای هرکدام یک بار باید کلیدی را فشار دهیم. هم‌چنین $2(n-x)$ بار باید کلید لامپ‌ها را فشار دهیم. تعداد کل حرکات$2(n-x)+x=2n-x$بار است.


اگر $x=0$ باشد همه‌ی لامپ‌ها روشن‌ هستند و نیازی به هیچ تغییر وضعیتی نیست. پس حداکثر تعداد مرحله‌ها، به ازای $x=1$ به‌دست می‌آید و $2n-1$ است.

</پاسخ>



  * [[سوال ۱۴|سوال بعد]]
  * [[سوال ۱۲|سوال قبل]]