سوال ۲۱

۱۰ لامپ خاموش در یک ردیف٬ به ترتیب پشت سرهم قرار دارند. در هر مرحله٬ یکی از لامپ‌های خاموش را روشن می‌کنیم. این کار را آن‌قدر انجام می‌دهیم تا تمام لامپ‌ها روشن شوند. می‌خواهیم به ترتیبی لامپ‌ها را روشن کنیم که هیچ‌گاه بین لامپ‌های روشن لامپ خاموش قرار نداشته باشد. به عنوان مثال٬ اگر لامپ‌های اول و سوم روشن باشند٬ لامپ دوم نیز باید حتماً روشن باشد. به چند طریق می‌توان ترتیبی برای روشن کردن لامپ‌ها ارائه داد٬ به طوری که شرط مذکور حفظ شود؟

  1. ۱۲۰
  2. ۵۱۲
  3. ۱۰۲۴
  4. ۵۰۴۰
  5. ۴۰۳۲۰

پاسخ

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

با استقرا روی $n$ ثابت می‌کنیم که به$2^{n-1}$حالت می‌توان $n$ لامپ را روشن کرد.لامپ‌ها را از چپ به راست از 1 تا $n$ شماره‌گذاری می‌کنیم.

پایه ی استقرا: برای$n=1$ برقرار است: تنها لامپ را روشن می‌کنیم.

گام استقرا: فرض کنیم برای $n-1$ لامپ، $2^{n-1}$ طریق وجود داشتهباشد. برای $n$ لامپ، لامپ شماره‌ی $n$ را در نظر نمی‌گیریم.به ازای هر روش در$n-1$، 2 حالت متناظر در $n$ارائه می‌دهیم.در هر روش،هر‌گاه لامپ $n-1$ام روشن شد،2 انتخاب داریم: یا اول لامپ $n$ را روشن می‌کنیم بعد دنباله حرکت‌های $n-1$ لامپ را ادامه می‌دهیم یا دنباله را ادامه داده و در‌نهایت به‌عنوان آخرین لامپ، لامپnام را روشن می‌کنیم.

درصورتی‌که هیچ لامپی با شماره‌ی کمتر از $n-1$ خاموش نباشد، تنها یک انتخاب داریم(روشن کردن لامپ nام) که متناظر با این دنباله حرکت است: $(1,2,3,…...,n-1,n)$. این دنباله را هم متناظر با دنباله‌ی جدید $(n,n-1,n-1,…..,2,1)$ در نظر می‌گیریم.

پس به ازای هر دنباله برای $n-1$ لامپ، 2 دنباله برای $n$ لامپ معرفی کردیم. بنابراین با $2^{n-1}$ روش می‌توانیم $n$ لامپ را روشن کنیم و جواب مسئله 512 می‌شود.