سوال ۲۲

جدول مختصات را در نظر بگیرید. در ثانیه‌ی صفر همه‌ی نقطه‌های آن سفیدند به غیر از نقطه‌ی (۱٫۰) که سیاه است. می‌دانیم که اگر در ثانیه‌ی $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$