سوال ۲۹
تعداد زیادی کارت مقوایی $3\times 3$ که با خط‌های افقی و عمودی به مربع‌های $1\times 1$ تقسیم شده است، به همراه یک میز بزرگ در اختیار داریم. در هر «مرحله» می‌توانیم تعدادی کارت را هم‌زمان روی میز قراردهیم به‌نحوی‌که این دو شرط رعایت شوند:
- کارت‌هایی را که در یک مرحله روی میز می‌گذاریم نباید هیچ قسمتی از یک‌دیگر را بپوشانند.
- حداقل یکی از مربع‌های $1\times 1$ هر یک از کارت‌هایی را که در مرحله‌ی $i$ام می‌گذاریم، باید دقیقاً روی یکی از مربع‌های $1\times 1$ یکی از کارت‌های مرحله‌ی $i-1$ قرار بگیرد.
اگر در ابتدا تنها یک کارت روی میز باشد، پس از ۴ مرحله حداکثر چند کارت روی میز خواهد بود؟
- ۵۴
- ۵۵
- ۸۷
- ۷۵
- ۱۶۵
پاسخ
گزینه (۴) درست است.
در مرحله‌ی اول ٬۴ در مرحله دوم ٬۹ در مرحله‌ی سوم ۲۵ و در مرحله‌ی چهارم ۳۶ کارت می‌توان بر روی میز با شرایط مسئله قرار داد که در این صورت تعداد کل کارت‌ها برابر $1+4+9+25+36$؛ یعنی ۷۵ خواهد شد.
به راحتی می‌توانید بررسی کنید که تعداد کل کارت‌های روی میز پس از $n$ مرحله برابر عبارت زیر می‌باشد:
$$ \lfloor \frac{3}{3} \rfloor^2 + \lfloor \frac{7}{3} \rfloor^2 +\lfloor \frac{11}{3} \rfloor^2 +\lfloor \frac{15}{3} \rfloor^2 + \lfloor \frac{19}{3} \rfloor^2 +...+\lfloor \frac{4n+3}{3} \rfloor^2$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
