چه تعداد لامپ روشن می ماند؟

Question

$1393$ لامپ داریم که همه در حالت اولیه خاموش هستند. این لامپ ها را از $1$ تا $1393$ شماره گذاری می کنیم. برای هر عدد صحیح و مثبت $k$ ، سوئیچ $p_{k}$ وضعیت خاموش و روشن لامپ هایی که شماره آنها مضربی از $k$ است را عوض می کند. سوئیچ های $p_{1} , p_{2} ,..., p_{1393}$ را متوالیا می زنیم. در آخر چند لامپ روشن می ماند؟

Answer 1

میدانیم هر عدد مانند $n$ تجزیه ای بصورت $n= p_{1} ^{ a_{1} } p_{2} ^{ a_{2} }... p_{t} ^{ a_{t} }$ دارد و تعداد مقسوم علیه های آن برابر $( a_{1}+1)( a_{2}+1)...( a_{t}+1)$ است.

طبق فرض سوال به ازای هر مقسوم علیه $n$ حالت لامپ شماره $n$ یکبار تغییر می کند و اگر تعداد نهایی این تغییر هافرد باشد آنگاه چراغ در نهایت روشن میماند(اول روشن، دوم خاموش، سوم روشن و....) لذا باید تعداد مقسوم علیه ها فرد باشد و این زمانی ممکن است که تمام توانها زوج باشند(اگر حتی یکی از آنها فرد باشد با $1$ جمع شده و مضرب $2$ یا همون عدد زوج را تولید میکند)

پس باید تعداد اعدادی رو بیابیم که در تجزیه ی آنها تواهای زوجی از اعداد اول وجود دارند.

یعنی داشته باشیم:

$$n=p_{1} ^{ 2b_{1} } p_{2} ^{ 2b_{2} }... p_{t} ^{ 2b_{t} } \Rightarrow n= (p_{1} ^{ b_{1} } p_{2} ^{ b_{2} }... p_{t} ^{ b_{t} } )^{2}$$

پس باید دنبال اعدادی بگردیم که توان دوم آنها از $1393$ کمتر باشند پس باید پایه از $38$ کمتر باشد و تعداد این اعداد $37$ است.