سوال ۲۱

گزینه‌ی (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 می‌شود.