سوال ۲۲
جدول مختصات را در نظر بگیرید. در ثانیه‌ی صفر همه‌ی نقطه‌های آن سفیدند به غیر از نقطه‌ی (۱٫۰) که سیاه است. می‌دانیم که اگر در ثانیه‌ی $t$ نقطه‌ی $(i,j)$ سیاه و اختلاف $i$ و $j$ برابر $k$ باشد٬ در ثانیه‌ی $t+۱$ علاوه بر نقطه‌ی $(i,j)$٬ نقطه‌های $(i+k,j)$٬ $(i-k,j)$٬ $(i, j+k)$ و $(i, j-k)$ نیز سیاه خواهند شد. در پایان ثانیه‌ی ۶ چند خانه‌ی سیاه در جدول موجود است؟
- ۱۳۹
- ۱۵۶
- ۱۹۱
- ۲۵۳
- ۵۴۶۱
پاسخ
گزینه (۳) درست است.
در ثانیه $i$ام $(i \geq 2)$ به تعداد $2^{i-1}$ نقطه سیاه بر روی خط $y=x$ و به تعداد $2^i$ نقطه سیاه بر روی خط $y=x-2^i$ اضافه می‌شود٬ بنابراین رابطه $U_n=U_{n-1}+2^n+2^{n-1}$ بین تعداد نقاط سیاه در دو مرحله $n$ و $n-1$ برقرار است. معلوم است که $U_1=5$ بنابراین:
$U_2=5+4+2=11$
$U_3=11+8+4=23$
$U_4=23+16+8=47$
$U_5=47+32+16=95$
$U_6=95+64+32=191$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
