سوال دوم (۳۲ نمره)

$n$ میز در یک ردیف، به‌ترتیب با شماره‌های ۱ تا $n$ قرار گرفته‌اند. روی هر یک از میزهای اول و آخر (میز شماره‌ی ۱ و میز شماره‌ی $n$)، یک آهن‌ربای الکتریکی نصب شده است. یک توپ فلزی نیز روی یکی از $n$ میز قرار دارد. ایراندخت قصد دارد با این وسایل بازی کند. او در هر گام از بازی، دقیقاً یکی از دو آهن‌ربا را روشن می‌کند و دیگری را خاموش می‌کند. فرض کنید در یک گام، آهن‌ربای میز $A$ روشن و آهن‌ربای دیگر خاموش باشد. در این شرایط، اگر توپ فلزی، روی همان میز $A$ باشد، هیچ اتفاقی رخ نمی‌دهد؛ در غیر این صورت اگر توپ فلزی روی میزی با فاصله‌ی $x$ از میز $A$ باشد، با روشن شدن آهن‌ربای میز $A$ در یک گام، توپ به میزی با فاصله‌ی $\lfloor \frac{x}{2} \rfloor$ از میز $A$ می‌رود که در این توصیف، فاصله‌ی بین میزهای $i$ و $j$ برابر با $|i - j|$ است. به عنوان مثال، اگر توپ فلزی روی میزهای شماره‌ی ۷ یا شماره‌ی ۸ باشد، با روشن شدن آهن‌ربای میز شماره‌ی ۱ در یک گام، توپ به سمت آن حرکت می‌کند و در میز شماره‌ی ۴ قرار می‌گیرد.

ثابت کنید ایراندخت می‌تواند توپ فلزی را از هر میزی، با تعدادی از گام‌های مذکور، به هر میز دیگری منتقل کند.