عبور از سد دفاعی ایران!

مسی و یارانش که خودشان را برای بازی امشب مقابل ایران آماده می کنند، پس از آنالیز بازی ایران دریافتند که نقطه‌ي قوت ایران در خط حمله‌ي این تیم است و در نتیجه تصمیم گرفتند دفاع خودشان را تقویت کنند. مربی آرژانتین سیستم دفاعیشان را به شکل تعدادی ستون کنار هم با ارتفاع‌ّهای طبیعی مدل کرده است. برای مثال این یک سیستم دفاعی ۵ ستونه است:

که به ترتیب از چپ ارتفاع ستون ها برابر ۳،۱،۳،۱،۵ می‌‌باشد. یک سیستم دفاعی قوی است، اگر به شکل مستطیل باشد. حال مربی آرژانتین می خواهد با قرار دادن کمترین تعداد مستطیل در شکل که هیچ دو مستطیلی با هم تلاقی نداشته باشند، شکل اولیه را به شکل یک مستطیل دربیاورد. برای مثال با ۳ مستطیل می توان شکل بالا را کامل کرد:

برای یک سیستم دفاعی، عدد $M$ را برابر با کمترین تعداد مستطیل لازم برای ایجاد یک سیستم دفاعی قوی، به طوری که ارتفاع مستطیل نهایی بیشتر ارتفاع ستون های اولیه باشد، می نامیم.(به عنوان مثال، برای شکل بالا مقدار $M$ برابر با ۴ ست) .

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 26003$ محاسبه شده‌اند.

$2$- الف (۱۱ نمره) : فرض کنید سیستم دفاعی ۲۴۲ ستونه ای داریم که ارتفاع ستون $i$-ام برابر با بزرگترین توانی از ۳ است که $i$ به آن بخش پذیر باشد. برای این حالت باقی مانده ی تقسیم $M^۴$ بر $\delta$ چقدر است؟

$2$- ب (۱۱ نمره) : فرض کنید یک سیستم دفاعی با ۲۰۰۰۰ ستون داریم و ارتفاع ستون ها از رابطه ی زیر به دست می آید:

• $h_۱ = ۱۲۳$
• $h_۲ = ۴۵۶$
• $h_i = (h_i-۱ + h_i-۲)\% ۱۲۳۴ + ۱$

برای این حالت باقی مانده ی تقسیم $M^۴$ بر $\delta$ چقدر است؟

$2$- ج (۱۱ نمره) : تمام سیستم های دفاعی ۲۰۰۰۰ ستونه که ارتفاع هر ستون حداکثر ۱۰۰۰۰ است را درنظر بگیرید. اگر برای همه این $۱۰۰۰۰^ ۲۰۰۰۰$ سیستم، عدد $M$ را محاسبه کنیم و عدد $K$ را برابر با مجموع همه این اعداد تعریف کنیم، باقیمانده تقسیم $K$ بر $\Delta$ چقدر است؟

• سوال بعد
• سوال قبل