چرخونک

علی کوچولو به تازگی یاد گرفته است خانه‌های زیر قطر اصلی یک جدول ‎$n \times n$‎ را حذف کند و آن را ‎$45$ درجه ساعت‌گرد بچرخاند. او به این شکل چرخونک تدبیر می‌گوید. ابتدا او در هر خانه‌ی چرخونک یک عدد می‌نویسد. سپس او در هر مرحله دو خانه که یک راس مشترک دارند و در یک ردیف افقی هستند را انتخاب می‌کند و مجموع آن‌ها را به خانه‌ی بالای‌شان اضافه می‌کند. سپس روی آن دو خانه یک ضربدر می‌کشد تا دیگر نتواند از آن‌ها استفاده کند و مقدارشان را تغییر دهد. حال علی می‌خواهد بداند در نهایت بیش‌ترین مقداری که خانه‌ی بالایی چرخونک تدبیر می‌تواند داشته باشد چیست؟ برای مثال به شکل زیر که یک چرخونک تدبیر ‎$4 \times 4$‎ می باشد، توجه کنید.

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

$3$- الف ($8$ نمره) : علی کوچولو چرخونک تدبیر یک جدول ‎$7 \times 7$‎ را کشیده است و به سطر اول آن از پایین به ترتیب از سمت چپ نام‌های ‎$1$ تا ‎$7$ ، به سطر دوم به ترتیب از سمت چپ نام های ‎$8$ تا $13$ و به خانه‌ی بالایی آن نام ‎$28$ را داده است. مقدار خانه ‎$i$‎اٌم را با ‎$q(i)$‎ نشان می دهیم و این مقدار از رابطه زیر محاسبه می شود‎.‎ $$q(1) = \Delta \% 10, q(n) =(q(\lfloor n/2\rfloor)‎ + ‎q(n-1)+1) \% 100$$ که علامت ‎$\%$‎ نشان دهنده باقی‌مانده می‌باشد. به علی بگویید بیش‌ترین مقداری که می‌تواند در نهایت به خانه‌ی بالا برساند چند است؟ اگر پاسخ این سوال برابر با ‎$M_1$‎ باشد، شما باید باقی‌مانده ‎$M_1$‎ بر ‎$\Delta$‎ را به عنوان پاسخ اعلام کنید.

$3$- ب ($12$ نمره) : فرض کنید چرخونک تدبیر یک جدول ‎$5000 \times 5000$‎ باشد و مقدار خانه‌های آن مانند مثلث خیام-پاسکال پر شده باشد (در مثلث خیام-پاسکال اگر یک خانه همسایه‌ی بالا چپ و بالا راست داشته باشد مقدارش برابر با جمع آن‌هاست و در غیر این صورت مقدارش برابر با یک می‌باشد)‎. فرض کنید بیش‌ترین مقداری که می‌تواند به خانه‌ی بالا برساند برابر ‎$M_2$‎ باشد، باقی‌مانده‌ی ‎$M_2$‎ بر ‎$\Delta$‎ را حساب کنید.

$3$- ج ($20$ نمره) : چرخونک تدبیر یک جدول ‎$5000 \times 5000$‎ که خانه‌های آن مانند قسمت ۱ شماره گذاری شده‌اند، یعنی خانه‌های ردیف پایین از ‎$1$ تا $5000$ و خانه‌ی بالایی ‎$\dbinom{5001}{2}$‎ نام گذاری شده است را در نظر بگیرید که مقدار خانه‌ای با نام ‎$i$‎ برابر ‎$q(i)$‎ است . فرض کنید بیش‌ترین مقداری که می‌توان به خانه‌ی بالا رساند برابر ‎$M_3$‎ باشد باقی‌مانده‌ی ‎$M_3$‎ بر ‎$\Delta$‎ را محاسبه کنید.

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