المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۰:سوال ۱۳

ماتریس و میانگین

یک ماتریس $1000\times 1000$ داریم که در ابتدا عدد سطر $i$ و ستون $j$ از آن برابر $i\times j$ است؛ مشابه جدول ضرب. سطرها و ستون‌ها از یک شماره‌گذاری می‌شوند.

می‌دانیم هر خانه‌ی این جدول با حداقل ۳ و حداکثر ۸ خانه مجاور است. با شروع از ثانیه‌ی اول، در انتهای هر ثانیه هر خانه مقدارش برابر مقدار جز صحیح میانگین مقدار ثانیه‌ی قبل خودش و خانه‌های مجاورش می‌شود.

برای مثال اگر در گوشه‌ی بالا راست جدول (سطر و ستون اول) عدد ۱ و در خانه سمت راستش (سطر اول ستون دوم) عدد ۲ و در خانه پایینی‌اش (سطر دوم ستون اول) عدد ۲ و در خانه‌ی پایین و راستی‌اش (سطر دوم و ستون دوم) عدد ۵ نوشته شده باشد، مقدار خانه بالا راست در ثانیه بعد برابر $\lfloor \frac{1+2+2+5}{4} \rfloor=2$ خواهد بود. دقت کنید که در هر ثانیه، هر خانه از روی مقادیر خودش و سایر خانه‌ها در ثانیه‌ی قبل مقدار می‌گیرد.

مشخص کنید که چند ثانیه طول می‌کشد تا جدول به حالتی برسد که مشابه حالت قبلش باشد (دیگر تغییر نکند)؟ به عبارت دیگر تعداد حالت‌های مختلف جدول (با احتساب حالت اولیه) که در طی این فرایند تولید می‌شوند چند تا است؟

اگر جواب مسئله مقدار $J$ باشد. باقی‌مانده‌ی تقسیم عدد $J^3$ بر $\Delta$ چند است؟


ابزار صفحه